Codeforces 432D Prefixes and Suffixes：KMP + dp

题目链接：http://codeforces.com/problemset/problem/432/D

题意：

　　给你一个字符串s，让你找出所有既是前缀又是后缀的子串，并输出它们分别出现了多少次。

题解：

　　先对原串求一次nex数组。

　　然后枚举位置i：

　　　　sub(k)表示前缀s[0 to k]

　　　　dp[i]表示sub(i)在原串s中的出现次数

　　　　假设nex[i] = a, nex[a] = b, nex[b] = c ... nex[z] = -1

　　　　则sub(a), sub(b), sub(c)...sub(z)均以s[i]结尾，dp[a...z]均+1。

　　然而一个一个加会T...

　　所以:

　　　　初始时所有的 dp = 1

　　　　每次：if(nex[i] != -1) dp[nex[i]] += dp[i]

　　　　一路传递下去就好。

　　最后从nex[len-1]开始往前跳nex。

　　对于每次跳到的nex，sub(nex)一定也是s的后缀。

　　此时输出它的出现次数dp[nex]。

　　另外因为要顺着输出，而nex是倒着跳的，所以先存到stack里再输出。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stack>

 #define MAX_N 100005

 using namespace std;

 int n;

 int dp[MAX_N];

 int nex[MAX_N];

 char s[MAX_N];

 void cal_nex(char *p,int len)

 {

     nex[]=-;

     int k=-;

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

     {

         while(k>- && p[i]!=p[k+]) k=nex[k];

         if(p[i]==p[k+]) k++;

         nex[i]=k;

     }

 }

 int main()

 {

     scanf("%s",s);

     n=strlen(s);

     cal_nex(s,n);

     for(int i=;i<n;i++) dp[i]=;

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

     {

         if(nex[i]!=-) dp[nex[i]]+=dp[i];

     }

     stack<int> stk;

     int p=n-;

     while(p!=-)

     {

         stk.push(p);

         p=nex[p];

     }

     cout<<stk.size()<<endl;

     while(!stk.empty())

     {

         int now=stk.top();

         stk.pop();

         cout<<now+<<" "<<dp[now]<<endl;

     }

 }

巴特西

Codeforces 432D Prefixes and Suffixes：KMP + dp

最新文章

热门文章