2015年4月21日 星期二

2015/04/21 Codeforces 494B. Obsessive String

/*
    先用KMP 查找字串
    接著DP答案
*/
// http://codeforces.com/problemset/problem/494/B
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MOD 1000000007

char s[300000], t[300000];
int f[300000];
int sn, tn;

int DP[300000][2];
bool OK[300000];

int main()
{
    scanf("%s %s", s, t);

    sn = strlen(s);
    tn = strlen(t);

    f[0] = -1;
    for(int ti = 1; ti < tn; ti++)
    {
        f[ti] = f[ti-1];
        while( f[ti] != -1 && t[ti] != t[f[ti]+1 ] ) f[ti] = f[f[ti] ];
        if( t[ti] == t[f[ti]+1 ] ) f[ti]++;
    }

    for(int si = 0, now = -1; si < sn; si++)
    {
        while( now != -1 && s[si] != t[now+1] ) now = f[now];
        if( s[si] == t[now+1] ) now++;

        if( now == tn-1 ) OK[si-tn+1] = true, now = f[now];
    }

    for(int si = 0, now = -1; si < sn; si++)
    {
        if( si-tn+1 >= 0 && OK[si-tn+1] ) now = si-tn+1;

        if( si ) DP[si][0] += DP[si-1][0]+DP[si-1][1]+1;
        else DP[si][0] = 1;

        DP[si][0] %= MOD;

        if( si ) DP[si][1] = DP[si-1][1];
        if( now != -1 ) DP[si][1] += DP[now][0];

        DP[si][1] %= MOD;
    }

    printf("%d\n", DP[sn-1][1]);
}

沒有留言:

張貼留言