数据结构实验之串一：KMP简单应用

川长思鸟来 2022-07-12 06:23 118阅读 0赞

Problem Description

给定两个字符串string1和string2，判断string2是否为string1的子串。  
Input

输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。  
Output

对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。  
Example Input

abc  
a  
123456  
45  
abc  
ddd  
Example Output

1  
4  
\-1  
Hint

Author

cjx

#include<stdio.h>
    #include<string.h>
    char a[1000001];
    char b[1000001];
    int next[1000001];
    void get(char a[], int next[])
    {
        int i, k;
        k = -1;
        next[0] = -1;
        int n = strlen(a);
        i = 0;
        while(i < n)
        {
            if(k == -1 || a[k] == a[i])
            {
                k++;
                i++;
                next[i] = k;
            }
            else
                k = next[k];
        }
    }
    int kmp(char a[], char b[])
    {
        int i, j, n, m;
        n = strlen(a);
        m = strlen(b);
        i = -1, j = 0;
        while(i < n && j < m)
        {
            if(j == -1 || a[i] == b[j])
            {
                i++;
                j++;
            }
            else
                j = next[j];
        }
        if(j > m - 1)
            return i - m;
        else
            return -1;
    }
    int main()
    {
        int x;
        while(scanf("%s%s", a, b) != EOF)
        {
            get(a, next);
            x = kmp(a, b);
            if(x != -1)
                printf("%d\n", x + 1);
            else
                printf("%d\n", x);
        }
        return 0;
    }