首页 > 代码库 > Obsessive String

Obsessive String

2024-08-08 00:29:44   209人阅读

Codeforces Round #282 (Div. 1)  B. Obsessive String

题目：链接

解题思路：

  1. 先用kmp找到所有的匹配点，时间复杂度O（n）
  2. 用dp[i]表示i是bk（题中的）时，字符串前i个字符的子串中的满足条件的总数
  3. 定义dp2[i]是前i个dp[i]的和，dp3[i]是前i个dp2[i]的和,m是匹配串的长度。
  4. 转移：当i不是匹配的结尾点时，dp[i]=dp[i-1]，反之，dp[i]=dp3[i]+i-m+1；
  5. 当i不是匹配的结尾点时，只要把bk从i-1点变到i点，故数量不变，dp[i]=dp[i-1]。
  6. 而当i是匹配的结尾点时，考虑ak（题中）可以取1，2，..，i-m+1（index从1开始）
  7. 故当k=1时，有i+m-1个（当时就由于没考虑到k=1的情况要单独算，一直过不了样例）
  8. 当k大于1时，当ak取j（1<=j<=i-m+1）时，bk-1可以取1,2，...，j-1，故有dp2[j-1]
  9. 而由ak取值，故有dp3[i-m]个，故dp[i]=dp3[i]+i-m+1
  10. 最后的结果就是dp2[n-1]，n为字符串长度。
  11. 注意取模
  12. 同时解题思路index是从1开始，我程序中index从0开始

代码如下：

 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=100010; 7 const int mod=1e9+7; 8 char s[maxn]; 9 char t[maxn];10 int f[maxn];11 int dp[maxn];12 int q[maxn];13 int dp2[maxn];14 int dp3[maxn];15 void getFail(char *P, int *f)16 {17     int m=strlen(P);18     f[0]=0;19     f[1]=0;20     for(int i=1;i<m;i++)21     {22         int j=f[i];23         while(j&&P[i]!=P[j])24         {25             j=f[j];26         }27         f[i+1]=P[i]==P[j]?j+1:0;28     }29 }30 void find(char *T,char *P,int *f)31 {32     int n=strlen(T);33     int m=strlen(P);34     getFail(P,f);35     int j=0;36     for(int i=0;i<n;i++)37     {38         while(j&&P[j]!=T[i])39         {40             j=f[j];41         }42         if(P[j]==T[i])43         {44             j++;45         }46         if(j==m)47         {48             q[i]=1;49         }50     }51 }52 53 54 int main()55 {56     while(scanf("%s%s",s,t)!=EOF)57     {58         int i;59         memset(q,0,sizeof(q));60         find(s,t,f);61         int n=strlen(s);62         int m=strlen(t);63         if(q[0])64         {65             dp[0]=1;66             dp2[0]=1;67             dp3[0]=1;68         }69         else70         {71             dp[0]=0;72             dp2[0]=0;73             dp3[0]=0;74         }75         for(i=1;i<=n;i++)76         {77             if(q[i]==0)78             {79                 dp[i]=dp[i-1];80             }81             else82             {83                 dp[i]=(dp3[i-m]+i-m+2)%mod;84             }85             dp2[i]=(dp[i]+dp2[i-1])%mod;86             dp3[i]=(dp2[i]+dp3[i-1])%mod;87         }88         printf("%d\n",dp2[n-1]);89     }90     91 92 93     return 0;94 }

AC如下：

Obsessive String


联系
我们