HDU 5763 Another Meaning

题目：Another Meaning

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5763

题意：每次给两个字符串s、t，字符串t 有两种意思，问s 字符串共有几种意思。比如s="ab"、t="a"，a有两种意思，假设为：原意a、异意*，那么ab有两种意思：ab、*b。

思路：

　　s字符串从1开始存

　　用dp[i] 表示s[1...i]有几种意思。假如s 末尾不等于t（或不看成t，即意思不变），那么dp[i]=dp[i-1]，如果s 末尾看成t（意思改变），那么dp[i]=dp[i-len]。

　　令dp[0]=1; len=t的长度

　　如果i 末尾等于t，那么dp[i]=dp[i-1]+dp[i-len]。如果不等，dp[i]=dp[i-1]。注意取模。

　　有一坑就是比赛的时候，代码里有next就一直CE，现在倒是不会了。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int next[10010];  //next数组
 4 char s[10010];    //模式串
 5 char st[1000010]; //原串
 6 void get_next()
 7 {
 8   next[0]=-1;
 9   next[1]=0;
10   //如果s里啥都没有，注意要加上特判
11   int i=1,j=0;
12   while(s[i])
13   {
14     if(s[i]==s[j]) next[++i]=++j;
15     else if(next[j]!=-1) j=next[j];
16     else i++;
17   }
18 }
19 
20 
21 
22 long long dp[100010];
23 int main()
24 {
25   int t,cas=1;
26   scanf("%d",&t);
27   while(t--)
28   {
29     scanf("%s",st+1);
30     scanf("%s",s);
31     get_next();
32     int len=strlen(s);
33     int i,j=0;
34     dp[0]=1;
35     for(i=1;st[i];)
36     {
37       if(st[i]==s[j])
38       {
39         j++;
40         if(s[j]==0)
41         {
42           dp[i]=(dp[i-1]+dp[i-len])%1000000007;
43         }
44         else dp[i]=dp[i-1];
45         i++;
46       }
47       else if(next[j]!=-1) j=next[j];
48       else
49       {
50         dp[i]=dp[i-1];
51         i++;
52       }
53     }
54     printf("Case #%d: %I64d
",cas++,dp[i-1]);
55   }
56   return 0;
57 }