CF1473B String LCM 题解

Content

如果一个字符串 \(s\) 由若干个字符串 \(t\) 拼接而成，则我们说 \(s\) 能被 \(t\) 整除。定义 \(s_1,s_2\) 的最短公倍串为可以同时被 \(s_1,s_2\) 的最短非空字符串。给定 \(T\) 对字符串 \(s_1,s_2\)，求出每对字符串的最短公倍串。

数据范围：\(T\in[1,2000],|s_1|,|s_2|\in[1,20]\)。

Solution

《记我用 1.81k 代码过了一道普及- 的题目》

由于数据范围小得可怜，我们可以先暴力求出 \(s_1,s_2\) 的所有非空子串，然后再判断两个字符串是否同时存在一个子串 \(s\)，使得 \(s_1,s_2\) 都能够被 \(s\) 整除。设我们找出来的这个字符串为 \(s_0\)，并设 \(s_1\) 由 \(a\) 个 \(s_0\) 拼成，\(s_2\) 由 \(b\) 个 \(s_0\) 拼接而成，那么只需要连续输出 \(\operatorname{lcm}(a,b)\) 个 \(s_0\) 就好了。

这种思路说起来容易，代码实现却不是那样简单。所以包括宏定义、头文件和快读在内，我打了 1.81k 的代码。

你可以去这里看到我和其他一些神仙的代码长度比较，由此可以看出我很菜qwq。

Code

string s1, s2, subs1[27], subs2[27], pos[27], ans;

int t, pos1[27], pos2[27], poscnt;

map<string, int> vis;

inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

inline int lcm(int a, int b) {return a * b / gcd(a, b);}

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	t = Rint;

	while(t--) {

		F(i, 1, 20) subs1[i] = ""; F(i, 1, 20) subs2[i] = ""; F(i, 1, 20) pos[i] = "";

		memset(pos1, 0, sizeof(pos1)), memset(pos2, 0, sizeof(pos2));

		vis.clear(); poscnt = 0; ans = "";

		cin >> s1 >> s2;

		int len1 = s1.size(), len2 = s2.size();

		F(i, 1, len1) subs1[i] = s1.substr(0, i);

		F(i, 1, len2) subs2[i] = s2.substr(0, i);

		F(i, 1, len1) {

			if(len1 % i) continue;

			string s = "";

			F(j, 1, len1 / i) s += subs1[i];

			if(s == s1) pos1[++pos1[0]] = len1 / i, pos[++poscnt] = subs1[i], vis[subs1[i]] = pos1[0];

		}

		F(i, 1, len2) {

			if(len2 % i) continue;

			string s = "";

			F(j, 1, len2 / i) s += subs2[i];

			if(s == s2 && vis[subs2[i]]) pos2[++pos2[0]] = len2 / i, ans = subs2[i];

		}

		if(ans == "") {puts("-1"); continue;}

		F(i, 1, lcm(pos1[vis[ans]], pos2[pos2[0]])) cout << ans;

		puts("");

	}

	return 0;

}

巴特西

CF1473B String LCM 题解

Content

Solution

Code

最新文章

热门文章