[POJ] 1226 Substrings.cpp

#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;
}