题解 | #2020#

简单的利用KMP算法进行比较，AC代码如下：

#include <iostream>
#define N 10006
using namespace std;


void SetNext(string s1,int next[],int size){
    next[0] = -1;
    int i = 0, j = -1;
    while(i < size){
        if(j == -1 || s1[i] == s1[j])next[++i] = ++j;
        else j = next[j];
    }
//    for(int i = 0; i < size; i++)cout << "next[" << i << "] = " << next[i] << endl;
}


int KMP(string s1,string s2){
    int sum = 0,i = 0,j = 0;
    int length1 = s1.length(),length2 = s2.length();
    int next[N];
    SetNext(s1,next,length1);
    while(i < length1 && j < length2){
        if(i == -1 || s1[i] == s2[j]){
            if(i == length1 - 1){
                j++;
                sum++;
                i = 0;
            }else{
                i++;
                j++;
            }
        }else{
            i = next[i];
        }
    }
    return sum;
}

int main(){
    int n;
    string s2,s1 = "2020";
    while(cin >> n){
        cin >> s2;
        cout << KMP(s1,s2) << endl;
    }
    return 0;
}