KMP是什么?

Prelude

  • prefix[S][l]\(S\)串的长度为\(l\)的前缀
  • suffix[S][l]\(S\)串的长度为\(l\)的后缀

孔乙己:你知道next array的四种写法吗?

  • next[i]表示什么?
  • \(nx[i]=max(l)\),其中\(l\)满足\(prefix[S][l]=suffix[prefix[S][i]][l]\)并且\(l<i\)
  • 那怎么写呢?容我三思……
  • 不如先从网上抄个板子一套,反正题目过了就行QAQ

别人家的板子

  • 这是个啥玩意啊?别人说这是个\(O(n+m)\)的东西,这地方不是套了两个循环吗,为什么是线性的啊?
  • \(emm...\)这个大佬说\(j\)每次增加只会加一,好像有点道理。
  • 应该是线性吧,应该没毛病。
  • 诶过题了,果然是线性!
  • 这个地方为什么\(next\)为什么要跳来跳去啊,仔细想想……
  • 感觉似乎好像也许是对的吧,不管了,反正题目过了……

一些解释

考虑一个点\(i\)

那么他有一个next[i]

这似乎是句废话

这个next[i]记录的是\(i\)串最长的前缀等于后缀的长度

又说了一句废话

其实next[i]可以用多种不同的解释方法

比如说除了长度之外,也可以解释成此前缀的位置

又双叒叕说了一句废话

我们可以从原串向这个前缀和后缀各连一条边,表明该前缀和该后缀虽然有不一样的位置,却有同样的值。

然后递归对后缀和前缀做同样的操作,然后我们就发现这是个完全二叉树(喵喵喵?),其中深度是沿next往前跳的次数。(在这棵树里每一层的串字面量都相等)

比如这样:

.
.
是男人就下一百层(删除线)
开发:tigertang(删除线)
.
.
===============> (5)
        ---------------> (4)
=======================> (2)
                ---------------> (6)
                        ...............> (7)
                -----------------------> (3)
=======================================> (1)

中间的每一层箭头都表示在原串的相应位置出现的某一个子串,给箭头的编号是用线段树式的编号(左儿子是\(2i\) ,右儿子是\(2i+1\))。这样解释起来就方便了。

\(lemma\):任意既是前缀又是后缀(严格的前缀与后缀,不能与原串重合)的串(的字面量),它一定可以通过不停地跳next被访问到。

\(proof\)case_1如果该串长度大于nx[i],等等,根据定义似乎好像没有这种情况QAQ

case_2如果该串长度等于nx[i],那就已经访问到咯

case_3如果该串长度小于nx[i],那么它必然是(2)的一个前缀,同时它也一定是(3)的一个后缀,当由于(2)(3)的字面量是相等的,所以它也一定是(2)的后缀,那么问题就转化为……不对,证明方向好像反了 重来重来

\(proof\):数规,先假设在\(j<i\)时任意既是前缀又是后缀的串都能被跳next访问到

case_1case_2同理

case_3这个串一定既是(2)的后缀也是(2)的前缀,而它又一定会被(2)的next访问到(数规)。

corner_case显然是对的。

这样我们就证明了通过递归访问next就能查询到所有既是前缀又是后缀的串。

怎么求next

.
.
是男人就原谅她(删除线)
开发:tigertang(删除线)
更新:把一个产品拖出去祭天(删除线)
.
.
===============> (5)
        ---------------> (4)
=======================> (2)
                ---------------> (6)
                        ...............> (7)
                -----------------------> (3)
=======================================> (1)

现在假设我们已经求出了所有\(<i\)next,现在我们要求next[i]

已知\(prefix[S][next[i-1]]=suffix[prefix[S][i-1]][next[i-1]]\)

(其实就是说(2)等于(3))

假设我们早就通过一个\(oracle​\)得知next[i]的值(愚蠢的人类啊

那么这个next[i]一定有一个性质是\(S[1..next[i]]=S[(i+1-next[i])..i]\)

如果next[i]>0的话就有\(S[1..(next[i]-1)]=S[(i+1-next[i])..i-1]\)

这样说来\(S[1..(next[i]-1)]\)这个前缀就一定是上一个串(\(i-1\))的后缀了。

那是不是就能通过在i-1不停地跳next找到它了?

奇技淫巧

如果next[1..i]都确定了,那么在\(i\)这个点匹配下一个字符\(c\)的匹配结果一定是确定的,所以可以记忆化嘞。

// hdu 6069
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50100, M = 110;
int n, m, k, nxl[M], nxr[M];
char S[N], T[M], r[N], l[N];
int reml[M][26], remr[M][26];
ll f[N][M], g[N][M];

inline int id(char c) { return c - 'a'; }

// string t as pattern
// we **have matched through x** and the next step is try to match c
// in position x+1 (in pattern t), maybe fail surely
//
// we have calculated the nx array of t
// 1. if calculated then return memory temp value
// 2. deal the corner case
// 3. if matched
// 4.
//    ( definition of kmp restricts that next pointers will search out all
//    the qualified suffies, which are prefies and suffies at the same time )
//    If failed then search nx[x]
//
//               (NULL)
//                 ^
//                ...  there upward arrows are next pointers
//                 |
//             ====>    (left) I'm also a prefix QAQ
//    ---->
//                 ^
//                 |
//        =========>   (left) this suffix is a prefix actually (and also the longest one)
//    --------->       (left) I am shadow (prefix in origin string) of the one above me
//                 ^
//                 |
//    =============>   (left) I'm the CURRENT and FULL string
//    ------------->
//   (for certain i, what will be searched along the next array)
//
//
//   NOTE: we will always match a continuous prefix in pattern t
//         jump along next pointers are means try to persist AL(long)AP of match string (S)
//         which is not included (and no need) in parameters

int next(int x, char c, char *t, int *nx, int (*rem)[26])
{
    int &res = rem[x][id(c)];
    if (res >= 0)
        return res;
    if (x == 0)
        return res = (t[1] == c);
    if (t[x + 1] == c)
        return res = x + 1;
    return res = next(nx[x], c, t, nx, rem);
}

void kmp(char *t, int len, int *nx, int (*rem)[26])
{
    nx[0] = nx[1] = 0;
    for (int i = 0; i <= len; i++)
        memset(rem[i], -1, sizeof rem[i]);
    for (int i = 2; i <= len; i++)
        nx[i] = next(nx[i - 1], t[i], t, nx, rem);
}

template <typename T>
void rev(T *t, int len)
{
    for (int i = 1; i <= len / 2; i++)
        swap(t[i], t[len - i + 1]);
}

void init()
{
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            f[i][j] = g[i][j] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = l[i]; j; j = nxl[j])
            f[i][j] = 1;
        f[i][0] = 1;
        for (int j = 0; j <= m; j++)
            f[i][j] += f[i - 1][j];
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = r[i]; j; j = nxr[j])
            g[i][j] = 1;
        g[i][0] = 1;
        for (int j = 0; j <= m; j++)
            g[i][j] += g[i + 1][j];
    }
    for (int i = n - 1; i >= 1; i--)
        g[i][m] += g[i + 1][m];
    for (int i = 2; i <= n; i++)
        f[i][m] += f[i - 1][m];
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k >> (S + 1) >> (T + 1);
        kmp(T, m, nxl, reml);
        l[0] = 0;
        for (int i = 1; i <= n; i++)
            l[i] = next(l[i - 1], S[i], T, nxl, reml);
        rev(S, n), rev(T, m);
        kmp(T, m, nxr, remr);
        r[0] = 0;
        for (int i = 1; i <= n; i++)
            r[i] = next(r[i - 1], S[i], T, nxr, remr);
        rev(r, n);
        init();
        while (k--)
        {
            int L, R;
            scanf("%d%d", &L, &R);
            ll ans = 0;
            for (int i = 0; i <= m; i++)
                ans += f[L][i] * g[R][m - i];
            printf("%lld\n", ans);
        }
    }
    return 0;
}