Oulipo

Plan A:KMP

题意很简单，就是通过 算法求得 数组，这点能力相信大家还是要掌握的，还没搞得很明白的去百度或者看我下面代码，我写的是和书上一模一样的，百度里面的可能是0结尾。这些没什么大区别，思路懂了就行。
还有就是 数组是可以求到最后一个的，这个老师上课没讲道过，因为我们上课讲的都是求第一次出现位置，所以匹配到指定长度就不需要再找了，直接 长度就行了。而这个地方，需要我们找到后再找下一个，所以我们要求到最后一个点的值。其实书上也求了，只是没有用而已。
如果暴力匹配每一个点

朴素匹配时间复杂度 O( ),N,M都是1e6，TLE妥妥的

KMP时间复杂度 O( ),线性阶，AC妥妥的。

字符串hash时间复杂度 O( )

Code

#include <stdio.h>
#include <string.h>

const int N = 1e6 + 7;
char a[N], b[N];
int lena, lenb;
int nxt[N];

void get_nxt() {  //求next数组
    int i = 0, j = -1;
    nxt[0] = -1;
    while (i < lenb) {
        if (j == -1 || b[j] == b[i])
            ++i, ++j, nxt[i] = j;
        else
            j = nxt[j];
    }
    /*for (int i = 0; i < lenb; ++i)
        printf("%d ", nxt[i]);
    puts("");*/
}

int main() {
    scanf("%s %s", a, b);
    lena = strlen(a), lenb = strlen(b);
    get_nxt();
    int cnt = 0;
    int i = 0, j = 0;
    while (i < lena) {
        if (j == -1 || a[i] == b[j])    ++i, ++j;
        else    j = nxt[j];
        if (j == lenb) {  //j匹配成功一次，次数加一
            ++cnt;
            //j = -1;   字符串B在A中出现位置不可重叠
            j = nxt[j];   //引用最后一个位置的nxt值，表明B在A中位置可重叠
        }
    }
    printf("%d\n", cnt);
    return 0;
}

/*
input: aaaa
       aa
output:3
*/

Plan B:字符串hash

我们后续课程也会提到 的概念，哈希是一种映射的概念，它可以在代替算法的前提下，简便的解决字符串匹配问题，其实如果你愿意去了解，字符串 比 算法好懂的多。如果把 取得好，或者多取几次，可以达到0误差，一般不卡 的题目，一遍 就行了。通过前缀和以及 自动溢出代替取模运算，可以高效便捷的解决字符串匹配问题。

Code

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 1e6 + 7;
const int base = 131;  //字符串hash值一般 131 or 13331 足够
ull has[N], po[N];
char a[N], b[N];
int lena, lenb;

int main() {
    scanf("%s %s", a + 1, b + 1); //a[0]='\0'，a[1]开始为字符串
    po[0] = 1;
    lena = strlen(a + 1), lenb = strlen(b + 1);
    for (int i = 1; i <= lena; ++i) {
        has[i] = has[i - 1] * base + a[i] - 'a';
        po[i] = po[i - 1] * base;
    }
    ull tmp = 0;  //b串hash值
    for (int i = 1; i <= lenb; ++i)
        tmp = tmp * base + b[i] - 'a';
    int cnt = 0;
    for (int i = 1; i + lenb - 1 <= lena; ++i)
        if (has[i + lenb - 1] - has[i - 1] * po[lenb] == tmp) //如果两串的hash值相等，我们就认为匹配成功
            ++cnt;
    printf("%d\n", cnt);
    return 0;
}