字符串匹配（KMP&BF）

字符串匹配

题目描述

设计一个程序，从一个主字符串中查找一个子字符串在主串中第一次出现的位置。主串和子串的长度不超过100。如果找不到，则输出-1.

程序输入说明

第一行输入一个整数N,说明需要进行匹配的实例数。
第二行输入第一组需要进行匹配的主串
第三行输入第一组需要匹配的子字符串。
以下各行按照上面两行的格式输入，直到输入了N组匹配实例。

程序输出说明

输出N行，每行显示对应的匹配组中子串在主串中第一次出现的位置。

程序输入样例

3
abaaaaaa
a
bacdeagb
ac
aaaa
bb

程序输出样例

1
2
-1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 typedef char* String;
 7 
 8 int len1,len2;
 9 char S[110];
10 char T[110];
11 
12 void get_next(String T,int *next){
13     int j = 0;
14     int i = 1;
15     next[1] = 0;
16     while( i<len2 ){
17         if(0==j || T[i]==T[j])
18         {
19             i++;
20             j++;
21             next[i] = j;
22         }
23         else{
24             j = next[j]; 
25         }
26     }    
27 }
28 
29 int Index_KMP(String S,String T,int pos){
30     int i=pos;
31     int j=1;
32     int next[255];
33     get_next(T,next);
34     while(i<=len1&&j<=len2){
35         if(j==0||S[i]==T[j]){
36             i++;
37             j++;
38         }
39         else{
40             j=next[j];
41         }
42     }
43     if(j>len2){
44         return i-len2;
45     }
46     else
47         return -1;
48 }
49 
50 int main(){
51     int n;
52     cin>>n;
53     while(n--){
54         scanf("%s%s",S+1,T+1);
55         len1 = strlen(S+1);
56         len2 = strlen(T+1);
57         printf("%d
",Index_KMP(S,T,1));
58     }
59     return 0;
60 }

BF算法

 1 //BF算法
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 char s[110],t[110];
 8 int len1,len2;
 9 
10 int main(){
11     int n;
12     cin>>n;
13     while(n--){
14         scanf("%s%s",s,t);
15         len1 = strlen(s);
16         len2 = strlen(t);
17         int i = 0,j = 0;
18         while( i < len1 && j < len2 ){
19             if( s[i] == t[j] ){
20                 i++;
21                 j++;
22             }
23             else{
24                 i = i-j+1;
25                 j = 0;
26             }
27         }
28         if( j == len2 )
29             cout<<i-j+1<<endl;
30         else
31             cout<<"-1"<<endl;
32     }
33     return 0;
34 }