HDU 6153 A Secret

CCPC网络赛的KMP模板题……

比赛期间因为被1003卡住了，这道题根本没时间去想……

本来一眼看去我也是想到AC自动机，只要吧字符串反转一下，就可以套用上一次的AC自动机直接求解。
但是模式串和匹配串都只有一个，建立AC自动机虽然可解，但有不必要的消耗。

这道题几乎卡掉了除了KMP以外的所有求这道题的其他解法。

题意：
给你两个串a , b，要你找出 b 串的所有后缀同时也是 a 串的子串。
然后按题意计算。

思路：
其实还是和上一道AC自动机有些类似之处。
但还是有很大不同，AC自动机可以在匹配的时候不断 fail 到前缀。
而KMP只能通过记录匹配，然后从后往前不断 next 累加。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int mod = 1e9 + 7;
const int max_n = 1e6 + 10;

char des[max_n], src[max_n];
int nxt[max_n], dlen, slen;
int num[max_n];

void getNext()
{
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < dlen)
        if (j == -1 || des[i] == des[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

void KMPCount()
{
    fill(num, num + dlen + 1, 0);
    int i, j = 0;
    ll ans = 0;
    getNext();
    for (i = 0; i < slen; i++) {
        while (j > 0 && src[i] != des[j])
            j = nxt[j];
        if (src[i] == des[j]) {
            j++;
            num[j]++;
        }
        if (j == dlen)
            j = nxt[j];
    }
    for (int i = dlen; i > 0; i--)
        num[nxt[i]] += num[i];
    for (int i = 1; i <= dlen; i++)
        ans = (ans + (1LL * num[i] * i) % mod) % mod;
    printf("%lld\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s", src, des);
        dlen = strlen(des), slen = strlen(src);
        reverse(des, des + dlen), reverse(src, src + slen);
        KMPCount();
    }
    return 0;
}