[問題] 字串搜尋的時間如何降低
題意=A: 1 25 68 58 456....(一串數字) B:25 68 C:25 36 98
要搜尋B C是否出現在A中
下面程式碼已經可以搜尋了
但是程式跑的不夠快 請問我需要怎麼修改程式才會跑的更快呢
謝謝大家
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define string_size 1000
#define search_size 1000
#define failure_size 100
#define temp_size 100
int kmp_search(int *str, int *sea ,int X,int Y);
int main(void)
{
int x;
int y;
int z;
int a;
int b;
int c;
int i;
int string[string_size];
int search[search_size];
int failure[failure_size];
int num[temp_size];
scanf("%d",&x);
for(y=0;y<x;y++)
{
int temp;
scanf("%d",&temp);
string[y]=temp;
}
scanf("%d",&a);
for(z=0,i=0;z<a;z++,i++)
{
scanf("%d",&b);
for(y=0;y<b;y++)
{
int temp;
scanf("%d",&temp);
search[y]=temp;
}
if(kmp_search(string,search,x,b) >=0 )
{
num[i]=kmp_search(string,search,x,b)+1;
}
else num[i]=-1;
}
for(c=0;c<a;c++)
{ if(num[c]>=0){
printf("Case %d: Yes, subsequence matched starting at position %d.\n",c+1,num[c]);
}
else printf("Case %d: No Match.\n",c+1);
}
system("pause");
return 0;
}
int kmp_search(int *str , int *sea, int X , int Y )
{
int i=0,j=0;
int len_string=X;
int len_search=Y;
int failure[failure_size];
while( i < len_string && j < len_search )
{
if(str[i]==sea[j])
{
i++;
j++;
}
else if(j==0) i++;
else j = failure[j-1] +1;
}
return( ( j == len_search )?( i-len_search ) : - 1 );
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.109.36
→
09/30 07:13, , 1F
09/30 07:13, 1F
推
09/30 08:57, , 2F
09/30 08:57, 2F
推
09/30 09:37, , 3F
09/30 09:37, 3F
→
09/30 09:53, , 4F
09/30 09:53, 4F
→
09/30 12:44, , 5F
09/30 12:44, 5F
推
09/30 18:11, , 6F
09/30 18:11, 6F
推
09/30 19:09, , 7F
09/30 19:09, 7F