1260: Oulipo

http://tjuacm.chaosheng.top/problem.php?id=1260
https://vjudge.net/problem/HDU-1686
这样写超时了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 10010;

string s1, s2;
int nextt[N];

void getNext(string s){
    int n = s.size();
    int i = 0, j = -1;
    nextt[i] = j;
    while(i < n){
        if(j == -1 || s[i] == s[j]){
            i++;
            j++;
            nextt[i] = j;
        }else{
            j = nextt[j];
        }
    }
} 

int kmp(string s2, string s1){
    int cnt = 0;
    getNext(s1);
    int n = s1.size(); 
    int m = s2.size();
    int i = 0, j = 0;
    while(i < m && j < n){
        if(j == -1 || s2[i] == s1[j]){
            i++;
            j++;
            if(j == n){//当模式串到达结尾时，回到指定位置，次数加1 
                j = nextt[j];
                cnt++;
            }
        }else{
            j = nextt[j];
        }
    }

    return cnt; //返回前缀的位置 
}

int main(){
    int t;
    cin >> t;
    while(t--){
        cin >> s1;
        cin >> s2;
        int n = s1.size(); 
        int m = s2.size();
        if(m == 0){
            printf("0\n");
            continue;
        }

        int res = kmp(s2, s1);  
        printf("%d\n", res);
    }
    return 0;
}

本来以为是kmp不对，改成了for循环扫描s2，但是发现还是超时。最后发现main的开头加上

    ios::sync_with_stdio(0);
    cin.tie(0);

就能通过了。而且上面超时的写法加上这句也能通过。
这两句的含义: https://blog.csdn.net/qq_45475271/article/details/107675845
参考：https://blog.csdn.net/duanghaha/article/details/80642298

for循环完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1000050;

string s1, s2;
int len1, len2;
int nextt[N];

void getNext(){
    int i = 0, j = -1;
    nextt[i] = j;
    while(i < len1){
        if(j == -1 || s1[i] == s1[j]){
            i++;
            j++;
            nextt[i] = j;
        }else{
            j = nextt[j];
        }
    }
} 

int kmp(){
    int cnt = 0;
    if(len1 == 1 && len2 == 1){
        if(s1[0] == s2[0])
            return 1;
        else return 0;
    }
    getNext();
    int i = 0, j = 0;
    for(i = 0; i < len2; i++){
        while(j > 0 && s2[i] != s1[j]){
            j = nextt[j];
        }
        if(s2[i] == s1[j]){
            j++;
        }
        if(j == len1){
            cnt++;
            j = nextt[j];
        }
    }

    return cnt; //返回前缀的位置 
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        cin >> s1 >> s2;
        len1 = s1.size(); 
        len2 = s2.size();
        int res = kmp();
        printf("%d\n", res);
    }
    return 0;
}