学步园

基本上是kmp，不过比较的时候有个技巧

废话不多说，先上代码

int Next[1000008];

void getNext(string s) {
    int len = (int)s.size();
    //VI Next(len);
    Next[0] = -1;
    int i=0, j=-1;
    while (i<len) {
        if (j==-1 || s[i]==s[j]) {
            Next[i] = j;
            i++; j++;
        }
        else
            j = Next[j];
    }
    //return Next;
}

int kmp(string ori, string pat) {
    int cnt = 0;
    getNext(pat);
    //VI Next = getNext(pat);
    int j = 0;
    for (int i=0; i<SZ(ori); i++) {
        while (i<SZ(ori) && j<SZ(pat)) {
            if (ori[i] == pat[j]) {
                j++; i++;
            }
            else {
                if (j == 0)
                    ++i;
                else
                    j = Next[j-1] + 1;
            }
        }
        if (j == SZ(pat)) {
            cnt++;
            //cout<<"i: "<<i<<endl;
            j = Next[j-1]+1;
            i = i-(SZ(pat)-j);
        }
    }
    return cnt;
}


int main() {
    ios::sync_with_stdio(false);
    //freopen("in.in","r",stdin);
    //int cnt;
    int t;
    cin>>t;
    string ori, pat;
    while(t--) {
        cin>>pat>>ori;
        cout<<kmp(ori,pat)<<endl;
    }

    return 0;
}

hihoCoder这个语言选择。。。啥时候能记忆一下用户常选语言【老CE也是伤不起啊尼玛】。。。G++版本略老啊。。。。

其实差不多就是个KMP比较！

但是如果你在kmp函数里面每次调用只匹配一次就不对了。。。。

我们来看一个坑爹的case：

ADA
ADADADA

ADA出现了几次呢？3次，起始点index分别是0, 2, 4，发现了吧，那你调用的时候难道是用kmp返回找到的起始index，然后origin串起始点i的下一个点i+1作为匹配的起始点再来一发匹配？如果这样交了就TLE了。。。。

我开始就是这样

int kmp(int ori_start, string ori, string pat) {
    // ...
    if (found)
        return index;
    return -1;
}

我很菜，之前一直以为这样写。。。但这样太不机智了。。。

你每次就移动一位，如果遇到了pat 很长很长，但是在ori中匹配了多次的情况，可是每次情况又间隔比较远

pat = WOZHENDESHIJURUOYA

ori = WOZHENDESHIJURUOXXXXXXWOZHENDESHIJURUOYAWOZHENDESHIJURUOXX

这种情况，假设比这长得多，间隔总是匹配着匹配着到最后发现不一样了，然后return -1，移动一位index，非常容易TLE【我也不知道他怎么卡的。。冏】

所以还要利用next数组

还说这种情况

ADA

ADADADA

你看，ADA匹配了第一次后该咋办捏。。。要怎么样才能更快匹配下一次。。。？

对！！就是想办法把ADA直接挪到下一个能更顺利匹配的地方【这个说法好像没啥用。。。】

第一次匹配中，最后一个匹配的都是A，说明那个A以及之前是匹配的，我们回到模式串上一个Next数组中获取到的index，是在D那里，从ori[3]开始，pat[1]开始继续匹配后面的就好了，节约了时间。如果数据比较大会体现得很清楚，总之意思就是移动的位数多了一点而已。。。

其实也不是为了说明白什么，大概自己能看懂留个印记就好啦。。。。