hdu 1686 KMP算法

╰+哭是因爲堅強的太久メ 2022-01-06 21:33 139阅读 0赞

题意：

求子串w在T中出现的次数。

kmp算法详解：http://www.cnblogs.com/XDJjy/p/3871045.html

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstring>
    #include <string>
    #include <cstdio>
    
    using namespace std;
    int lenp;
    int lens;
    void getnext(int *next, char *p)
    {
        int j = 0, k = -1;
        next[0] = -1;
        while(j < lenp)
        {
    
            if(k == -1 || p[j] == p[k])
            {
                j++;
                k++;
                next[j] = k;
            }
            else
                k = next[k];
        }
    }
    
    char s[1000100], p[10100];
    int next[10100];
    int main(void)
    {
        int N;
        scanf("%d", &N);
        while( N-- )
        {
    
            scanf("%s", p);
            scanf("%s", s);
            lens=(int)strlen(s);
            lenp=(int)strlen(p);
    
            getnext(next, p);
            int i = 0;
            int j = 0;
            int sum = 0;
    
            while(i < lens&&j<lenp)
            {
                //printf("%d %d %c %c\n",i,j,s[i],p[j]);
                if( j == -1 || s[i] == p[j] )
                {
    
                    i++;
                    j++;
                }
                else
                {
                    j = next[j];
                }
                //printf("#%d %d %c %c\n",i,j,s[i],p[j]);
                if( j >=lenp)
                {
                    sum++;
                    j = next[j];/!!!!!!!!!!
                    //printf("%d %c %c\n",sum,s[i],p[j]);
                }
            }
            printf("%d\n", sum);
        }
        return 0;
    }

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    #define L1 1000005
    #define L2 10005
    
    int next[L2], len1, len2, res;
    char s[L1], p[L2];
    
    void get_next ()
    {
        int j = 0, k = -1;
        next[0] = -1;
        while (j < len2)
        {
            if (k == -1 || p[j] == p[k])
            {
                j++, k++;
                next[j] = k;
            }
            else k = next[k];
        }
    }
    void kmp (int pos)
    {
        int i = pos, j = 0;
        while (i < len1 && j < len2)
        {
            //printf("%d %d %c %c\n",i,j,s[i],p[j]);
            if (j == -1 || s[i] == p[j])
            {
                i++, j++;
            }
            else j = next[j];
            //printf("#%d %d %c %c\n",i,j,s[i],p[j]);
            if (j >= len2)
                    res++, j = next[j];    //神奇之处，效率大增
        }
    }
    int main()
    {
        int t;
        scanf ("%d", &t);
        while (t--)
        {
            res = 0;
            scanf ("%s%s", p, s);
            len1 = strlen (s);
            len2 = strlen (p);
            get_next ();
            kmp (0);
            printf ("%d\n", res);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/XDJjy/p/3923097.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/2d7ebf98cf444134bf2303d131d29ca3.png