朴素算法解答，用Python做

如图第七题，用朴素算法来做一下，谢谢

我有文章写过这个，你可以去看看，我就不复制过来了，

﹉

#include
#include
#include
#include
#include
#include
#include
#include

typedef long long ll;
const int maxn = 10005;
string s, p;
int Next[maxn];
int cnt;
int slen, plen;

void getfail() {
memset(Next, 0, sizeof(Next));
Next[0] = 0; Next[1] = 0;
for (int i = 1; i < plen; i++) {

    int j = Next[i];           //j:代表能够匹配的下标 

    while (j && p[i] != p[j]) {//弹出来的j 不是0 就是两个串相同的 最大下标 也就是公共长度
        j = Next[j];
    }
    Next[i + 1] = (p[i] == p[j]) ? j + 1 : 0;
}

}

void kmp() {
int last = 0;
slen = s.size();
plen = p.size();
getfail();//求next 最大前缀
int j = 0;
for (int i = 0; i < slen; i++) {

    /*假如说 在下标 == 4的时候 与主串不匹配 它就会从进入while语句 找到s[i] == p[j]
        返回next【j】 然后从next【j】继续匹配

        举个例子：
        i下标  0 1 2 3 4 5 6 7 8 9
        主串   A B C A B C D H I J

        j子串  A B C A B B _
        nex的  0 0 0 0 1 2 0

        当i = 5时 此时j = 5 显然不匹配 进入while-- > 更新：j = 2 -- > s[i] = p[j] -- > 退出  
        以此类推 一直寻找......


    */
    while (j && s[i] != p[j]) {//不同就往前 0 就重新找
        j = Next[j];          //不然 找到当前不符合的位置 前缀又相等的情况
    }


    if (s[i] == p[j]) {     //紧随其后  如果找到同的 继续移动 j 判断下一个
        j++;
    }

    if (j == plen) {//计数 根据自己的需要 自己改
            cnt++;    //给两道题你们就知道怎么改了HDU 2087，1686
    }

}

}
int main() {
//freopen("888.txt", "r", stdin);
cin >> s >> p;
kmp();
printf("%d\n", cnt);
return 0;
}
﹉