1.簡單的字元串比對函數
簡單的字元串比對很簡單，就是一個兩重循環。
算發一：
#include<stdio.h>
#include<string.h>
char s[51],t[11];
int next[11];
int cnt[11];
void index(char*s,char *t,int pos)
{
int i,j,k;
int x = 0;
int len1 = strlen(s);
int len2 = strlen(t);
for(i=pos;i<len1;i++)
{
k = i;
for(j=0;j<len2;j++)
{
if(s[k++]!=t[j])
break;
}
if(j>=len2)
{
cnt[x++] = i;
}
}
}
int main(void)
{
memset(cnt,-1,11*sizeof(int));
gets(s);
gets(t);
int pos;
scanf("%d",&pos);
index(s,t,pos);
for(int i=0;cnt[i]!=-1;i++)
{
printf(" %d",cnt[i]);
}
return 0;
}
下面分析其複雜度：
除了在index2，index4，index6，index10四處字元串比較了多次外，在其他地方字元串隻比較了一次，總共的比較次數為（n-m+1）+（m-1）+others，others為紅色的部分，也就是說其複雜度接近O(n+m)。
假設主串的長度為n，模式串的長度為m，在最壞情況下，對于主串(n-m+1)中的每一個字元，都要和模式中的字元比對m次，後面的每個字元的比對次數總共為（1+2+…+(m-1)）=m(m-1)/2，則總的比對次數為(n-m+1)*m+ m(m-1)/2，也即算發複雜度為O(n*m)。
上面這種方法比較的直覺和簡單，但是複雜度卻很高，效率低下，很難應用于實際，下面有個改進的版本，功能是輸出第一次出現子串的索引。
算發二：
#include <stdio.h>
#include <string.h>
char s[51],t[11];
int next[11];
int index(char *s,char *t,int pos)
{
int i =pos-1;
int j = 0;
int len1= strlen(s);
int len2 =strlen(t);
while(i<len1&&j<len2)
{
if(s[i]==t[j])
{
i++;
j++;
}
else
{
i -=j-1;
j =0;
}
}
if(j>=len2)
{
returni-len2;
}
else
return-1;
}
int main(void)
{
gets(s);
gets(t);
int pos;
scanf("%d",&pos);
int no =index(s,t,pos);
if(no>0)
printf("String s contains substring t at index of %d~~\n",no);
else
printf("String s does not contain substring t~~\n");
return 0;
}
下面讓我們來分析其複雜度，
除了在index2，index4，index6，index10四處字元串比較了多次外，在其他地方字元串隻比較了一次，假設最終查找到子串的位置為index，在一次查找過程中，最終的比較次數為(index+len2-1)+others,這個others就是之前有過的多次比較的結果。其複雜度接近O(n+m)。在最壞的情況下，其複雜度也是O(n*m)。
算發三：
#include <stdio.h>
#include <string.h>
char s[51],t[11];
int next[11];
int cnt[11];
void index(char *s,char *t,int pos)
{
intx=0;
int i = pos-1;
int j = 0;
int len1 = strlen(s);
int len2 = strlen(t);
for(i=pos-1;i<len1;)
{
while(i<len1&&j<len2)
{
if(s[i]==t[j])
{
i++;
j++;
}
else
{
i -= j-1;
j = 0;
}
}
if(j>=len2)
{
cnt[x++] = i-len2;
i -= len2-1;
j = 0;
}
}
}
int main(void)
{
memset(cnt,-1,11*sizeof(int));
gets(s);
gets(t);
int pos;
scanf("%d",&pos);
index(s,t,pos);
for(int i=0;cnt[i]!=-1;i++)
{
printf(" %d",cnt[i]);
}
printf("\n");
return 0;
}