POJ-3080-Blue jeans(KMP, 暴力)

链接:

https://vjudge.net/problem/POJ-3080#author=alexandleo

题意:

给你一些字符串，让你找出最长的公共子串。

思路:

暴力枚举第一个串的子串,挨个匹配接下来的所有串.

找出最长子串中, 字典序最小的.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#include <iostream>

#include <sstream>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 1e6+10;

int Next[MAXN];

string s[20];

int n;

void GetNext(string p)

{

    int len = p.length();

    Next[0] = -1;

    int j = 0;

    int k = -1;

    while (j < len-1)

    {

        if (k == -1 || p[k] == p[j])

        {

            ++k;

            ++j;

            Next[j] = k;

        }

        else

            k = Next[k];

    }

}

bool Kmp(string ss, string p)

{

    int lens = ss.length();

    int lenp = p.length();

    int i = 0, j = 0;

    while (i < lens && j < lenp)

    {

        if (j == -1 || ss[i] == p[j])

        {

            i++;

            j++;

        }

        else

            j = Next[j];

    }

    return j == lenp;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        string res = "";

        cin >> n;

        for (int i = 1;i <= n;i++)

            cin >> s[i];

        int len = s[1].length();

        for (int i = 0;i < len;i++)

        {

            for (int j = i;j < len;j++)

            {

                string tmp(s[1], i, j-i+1);

                GetNext(tmp);

                bool flag = true;

                for (int k = 2;k <= n;k++)

                {

                    if (!Kmp(s[k], tmp))

                    {

                        flag = false;

                        break;

                    }

                }

                if (flag)

                {

                    if (tmp.length() > res.length())

                        res = tmp;

                    if (tmp.length() == res.length() && tmp < res)

                        res = tmp;

                }

            }

        }

        if (res.length() >= 3)

            cout << res << endl;

        else

            cout << "no significant commonalities" << endl;

    }

    return 0;

}