poj 3461 - Oulipo 经典kmp算法问题

2017-08-13 19:31:47

writer：pprp

对kmp算法有了大概的了解以后，虽然还不够深入，但是已经可以写出来代码，（可以说是背会了）

所以这道题就作为一个模板，为大家使用吧。

题目大意：给你一个子串P和一个主串S，求在主串中有多少个子串？

代码如下：（需要注意的点我都标记好了，两个函数可以直接用）

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

int ans;

const int maxn = ;

int next[maxn];

char S[maxn],P[maxn];

//构造next数组

void get_next()

{

      int i =  ;

      int j = -;

      int lenp = strlen(P); //要用额外变量，如果写在while循环中就会TLE

      next[] = -;

      while(i < lenp)

      {

            if(j == - || P[i] == P[j])

            {

                  i++;

                  j++;

                  next[i] = j;

            }

            else

                  j = next[j];

      }

}

//开始模式匹配

void kmp()

{

      int i =  ;

      int j =  ;

      //要用额外变量，如果写在while循环中就会TLE

      int lens = strlen(S);

      int lenp = strlen(P);

      get_next();  //这个构造不能忘记写

      while(i < lens && j < lenp)

      {

            if(j == - || P[j] == S[i])

            {

                  i++;

                  j++;

            }

            else

                  j = next[j];

            if(j == lenp)

            {

                  ans++;

                  j = next[j];

            }

      }

}

int main()

{

    int cas;

    cin >> cas;

    while(cas--)

    {

          ans = ;

          memset(next,,sizeof(next));

          scanf("%s%s",P,S);

          kmp();

          cout << ans << endl;

    }

    return ;

}