POJ 2752 Seek the Name, Seek the Fame kmp(后缀与前缀)

时间：2023-03-08 17:23:06
POJ 2752 Seek the Name, Seek the Fame kmp(后缀与前缀)

题意:

给你一个串T,找出串T的子串,该串既是T的前缀也是T的后缀。从小到大输出所有符合要求的串的长度。

分析:

首先要知道KMP的next[i]数组求得的数值就是串T中的[1,i-1]的后缀与串T中的[0,i-2]前缀的最大匹配长度。         所以next[m](m为串长且串从0到m-1下标)的值就是与后缀匹配的最大前缀长度(想想是不是)。

next[next[m]]也是一个与后缀匹配的前缀长度,,,依次类推即可。

题解来自饶齐：http://blog.csdn.net/u013480600/article/details/23024781

//作者:1085422276

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

//#include<bits/stdc++.h>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

const int inf = ;

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    ll temp,p;

    if(b==)

    {

        x=;

        y=;

        return a;

    }

    p=exgcd(b,a%b,x,y);

    temp=x;

    x=y;

    y=temp-(a/b)*y;

    return p;

}

//*******************************

char a[];

    int maxl[],p[];

int main()

{

     while(gets(a)!=NULL)

     {

         int n=strlen(a);

          memset(p,,sizeof(p));

          int j=;

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

          {

              while(j>&&a[j]!=a[i])j=p[j];

              if(a[j]==a[i])j++;

              p[i+]=j;

          }

          int cnt=;

          maxl[++cnt]=n;

          int i=n;

          while(p[n])

          {

              maxl[++cnt]=p[n];

              n=p[n];

          }

          for(int i=cnt;i>;i--)

          {

             printf("%d ",maxl[i]);

          }

          printf("%d\n",maxl[]);

     }

    return ;

}

代码

相关文章