题目链接：
codeforces 494B
题目大意：
给出两个字符串，问第一个字符串由多少种方法提取出一些子串使这些子串中都包含t模式串。
题目分析：定义状态dp[i]表示前i个字符由多少种方法得到符合要求的字符串组。
解释： 首先dp[i-1]代表的是不重新构造新的子串的情况，那么也就是前面如果被选取，那么当前位必选，前一位空缺，那么当前位必空缺，所以情况数就等于dp[i-1]之后考虑l是保证当前段内包含t的最大标号，固定了右侧位置，然后枚举左位置，，因为会比之前的情况多出一种只保留串本身的情况，所以是dp[j]+1,然后提取出来之后就变成最后加上l。 AC代码：;char s[MAX],t[MAX];int mark[MAX];const int mod = 1e9+7;int dp[MAX];int sum[MAX];void get_next ( char p[] , int next [] ){int i = 0 , k = -1 , len = strlen ( p );next[0] = -1;while ( i < len )if ( k == -1 || p[i] == p[k] )i++,k++,next[i]=k;else k = next[k];}void match ( char s[] , char p[] ){memset ( mark , 0 , sizeof ( mark ) );int next[MAX];get_next ( p , next );int len1 = strlen ( s );int len2 = strlen ( p );int i = 0 , j = 0;while (i < len1 ){if ( j == -1 || s[i] == p[j] ) i++ , j++;else j = next[j];if ( j == len2 )mark[i] = i-len2+1;}}int main ( ){while ( ~scanf ( “%s” , s ) ){scanf ( “%s” , t );match ( s , t );sum[0] = dp[0] = 0;int n = strlen ( s );for ( int i = 1 ; i <= n ; i++ )if ( !mark[i] )mark[i] = mark[i-1];for ( int i = 1 ; i <= n ; i++ ){dp[i] = dp[i-1];int l = mark[i];if ( !l ) continue;dp[i] += (sum[l-1]+l)%mod;dp[i] %= mod;sum[i] = sum[i-1] + dp[i];sum[i] %= mod;}printf ( “%d\n” , dp[n] );}}
好好扮演自己的角色，做自己该做的事
