POJ 3080 Blue Jeans KMP

//暴力搜即可
#include<iostream>
#include<cstring>
#include<string>
using namespace std;

char s[10][61];  //原字符串
string ss[61][61];   //0串的所有子串
int nex[61][61][65];
int maxn = -1;
string ans; 

void getNex(int l, int r)
{
    int len = ss[l][r].length();
    nex[l][r][0] = -1;
    int i = 0, j = -1;
    while(i < len)
    {
        if(j == -1 || ss[l][r][i] == ss[l][r][j])
        {
            i++, j++;
            nex[l][r][i] = j;
        }
        else j = nex[l][r][j];
    }
}


void KMP(int l, int r, int n)  //n是串个数
{
    int k;
    string st = ss[l][r];
    int len = st.length();
    for(k = 1; k < n; k++)
    {
        int i = 0, j = 0;
        while(i < 60 && j < len)
        {
            if(j == -1 || s[k][i] == st[j]) i++, j++;
            else j = nex[l][r][j];
        }
        if(j != len) break;
    }

    if(k == n)
    {
        if(len > maxn)
        {
            maxn = len;
            ans = st;
        }
        else if(len == maxn)
            ans = st < ans ? st : ans;
    }
}

int main()
{
    int N;
    scanf("%d", &N);
    while(N--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%s", s[i]);
        for(int i = 0; i < 58; i++)   //枚举所有子串
            for(int j = i+2; j < 60; j++)
            {
                ss[i][j].clear();
                for(int k = i; k <= j; k++) 
                    ss[i][j] += s[0][k];
            }

        for(int i = 0; i < 58; i++)
            for(int j = i+2; j < 60; j++)
                getNex(i, j);

        maxn = 0;
        ans.clear();
        for(int i = 0; i < 58; i++)
            for(int j = i+2; j < 60; j++)
                KMP(i, j, n);
        if(maxn < 3) printf("no significant commonalities\n");
        else cout << ans << endl;
    }
    //system("pause");
    return 0;
}
上一篇:set和map


下一篇:html设置滑动条