POJ 1226 Substrings

想法：
    先將全部的字串依照length由小到大排序，把最短的那個字串拿來枚舉，由長到短枚舉該字串的所有substring，以sample input第二個case舉例，最短的字串為"rose"，枚舉substring "rose", "ros", "ose", "ro", "os"...。
    每次枚舉到一個substring後，記得還有反轉sub_inverse，把substring和sub_inverse拿來和其他字串(除了最短的字串以外的字串)比較，這邊我是套KMP Algorithm，如果其他字串全部都找的到substring或sub_inverse的話，表示找到答案，輸出該substring的長度。

	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	string str[105];
	int pi[105]; // prefix index for substring
	int pi_inverse[105]; // prefix index for inverse substring
	void Prefix(const string &P, int pi[]);
	bool KMP(const string &P, const string &T, int pi[]);
	bool cmp(const string &A, const string &B) {return A.size() < B.size();}
	int main()
	{
	ios::sync_with_stdio(false);
	int Case, N;
	cin >> Case;
	while (Case--) {
	cin >> N;
	int min_length = 999, min_index;
	for (int i = 0; i < N; ++i)
	cin >> str[i];
	sort(str, str + N, cmp);
	for (int ans = str[0].length(); ans >= 0; --ans) {
	bool has_ans = false;
	for (int i = 0; i + ans <= str[0].length(); ++i) {
	string sub = str[0].substr(i, ans);
	string sub_inverse = sub; reverse(sub_inverse.begin(), sub_inverse.end());
	Prefix(sub, pi);
	Prefix(sub_inverse, pi_inverse);
	bool ok = true;
	for (int k = 1; k < N && ok; ++k)
	if (!KMP(sub, str[k], pi) &&
	!KMP(sub_inverse, str[k], pi_inverse))
	ok = false;
	if (ok == true) {has_ans = true; break;}
	}
	if (has_ans) {cout << ans << endl; break;}
	}
	}
	}
	void Prefix(const string &P, int pi[])
	{
	pi[0] = -1;
	for (int q = 1; q < P.length(); ++q) {
	if (P[q] == P[pi[q-1]+1])
	pi[q] = pi[q-1]+1;
	else if (P[q] == P[0])
	pi[q] = 0;
	else
	pi[q] = -1;
	}
	}
	bool KMP(const string &P, const string &T, int pi[])
	{
	int q = -1;
	for (int i = 0; i < T.length(); ++i) {
	while (q >= 0 && P[q+1] != T[i])
	q = pi[q];
	if (P[q+1] == T[i])
	++q;
	if (q == P.length()-1)
	return true;
	}
	return false;
	}

view raw [POJ] 1226 Substrings.cpp hosted with ❤ by GitHub