程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4763（KMP的應用）

hdu4763（KMP的應用）

編輯：C++入門知識

題意：給一個字符串，問最長的一個子串A，他是前綴，同時是後綴，並且中間也出現過A。並且出現的三個A都不沒有重疊部分。

解法：先KMP求出失配數組，然後將所有的是後綴且是前綴的打上標記，然後遍歷整個next數組，（對於每個位置的next來說，一直next向前取就是找到此前綴的一個個是整個字符串前綴的後綴，比較繞）暴力枚舉判斷每個串的所有匹配前綴的後綴是否合法。

代碼：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define eps 1e-8
typedef long long LL;

int next1[1001000];
void getNext(char *s)
{
    int len=strlen(s);
    int i=0;
    int j=next1[0]=-1;
    while(i>t;
    while(t--)
    {
        memset(rem,0,sizeof rem);
        scanf("%s",s);
        getNext(s);
        int len=strlen(s);
        int tool=next1[len];
        while(tool)
        {
            rem[tool]=1;
            tool=next1[tool];
        }
        int out=0;
        for(int i=len-1; i>1; i--)
        {
            int t=i;
            while(t!=-1)
            {
                if(rem[next1[t]]&&len-next1[t]>=i&&i-next1[t]>=next1[t])
                {
                    out=max(out,next1[t]);
                    break;
                }
                t=next1[t];
            }
        }
        cout<