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

迈不过友情╰ 2022-07-17 01:41 84阅读 0赞

## 题目描述 ##

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

## 输入 ##

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

## 输出 ##

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

## 示例输入 ##

abc
    a
    123456
    45
    abc
    ddd

## 示例输出 ##

1
    4
    -1

## 提示 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    struct hh 
    {
    	char data[1000000];
    	int len;
    };
    void Getnext(struct hh *t,int next[])
    {
    	int j=0,k=-1;
    	next[0]=-1;
    	while(j<t->len)
    	{
    		if(k==-1||t->data[j]==t->data[k])
    		{
    			k++;
    			j++;
    			if(t->data[j]!=t->data[k])
    				next[j]=k;
    			else
    				next[j]=next[k];
    		}
    		else
    			k=next[k];
    	}
    }
    int KMP(struct hh *s,struct hh *t)
    {
    	int next[1000000],i=0,j=0;
    	Getnext(t,next);
    	while(i<s->len&&j<t->len)
    	{
    		if(j==-1||s->data[i]==t->data[j])
    		{
    			i++;
    			j++;
    		}
    		else
    			j=next[j];
    	}
    	if(j>=t->len)
    		return (i-t->len+1);
    	else
    		return -1;
    }
    void main()
    {
    	struct hh *s,*t;
    	s=(struct hh *)malloc(sizeof(struct hh));
    	t=(struct hh *)malloc(sizeof(struct hh));
    	while(scanf("%s\n%s",&s->data,&t->data)!=EOF)
    	{
                    s->len=strlen(s->data);
    		t->len=strlen(t->data);
    		printf("%d\n",KMP(s,t));
    	}
    }