POJ - 3461 Oulipo(KMP)

迈不过友情╰ 2022-06-05 08:47 166阅读 0赞

[点我看题][Link 1]

//这两天看了下KMP，能够去理解要怎么跳，但总感觉还缺点什么东西，只能通过刷一些题目来找找感觉

题意：给一个串P，问在串T中出现了几次。

分析：典型的KMP模板题

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    const int maxn = 1e6+10;
    const int maxm = 1e4+10;
    int n,m;//主串与模式串的长度
    char T[maxn];//主串
    char P[maxm];//模式串
    int nxt[maxm];//前缀表
    
    //建前缀表
    void GetNext()
    {
         int i = 0, j = -1;
         nxt[0] = -1;
         while( i < m)
         {
             if( j == -1 || P[i] == P[j])
                nxt[++i] = ++j;
            else
                j = nxt[j];
         }
    }
    
    //找出现了多少次
    int KMPCount()
    {
        if( n == 1 && m == 1)
            return T[0] == P[0] ? 1 : 0;
    
        GetNext();
        int ans = 0;
        int i = 0, j = 0;
        for( ; i < n; i++)
        {
            while( j > 0 && T[i] != P[j])
                j = nxt[j];
            if( T[i] == P[j])
                j++;
            if( j == m)
                ans++, j = nxt[j];
        }
        return ans;
    }
    
    int main()
    {
        int T_T;
        scanf("%d",&T_T);
        while( T_T--)
        {
            scanf("%s",P);
            scanf("%s",T);
            n = strlen(T);
            m = strlen(P);
            printf("%d\n",KMPCount());
            for( int  i = 0; i <= m; i++)
                printf("%d\n",nxt[i]);
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3461