以下是引用九转星河在2016-12-10 21:15:30的发言:
其实原型是p1-(p2-ps);p2-ps为p2为子串的长度,因此p2-ps是个定值
哦,漏看了,p2与ps是相对的。
试用Sunday算法写一个strstr()
/*
字符串模式匹配(Sunday算法)
模式串.1234235612356
子串...1235
从左至右匹对,4与5不匹对。
再看4后面的2,从右至左看看2是否在子串中。
1234235612356
4后面的2是在子串中,将子串中的2对着4后面的2。
...1235
再从4开始从左至右匹对,4与1不匹对。
看5后面的6,从右至左看看6是否在子串中。
5后面的6不在子串中,6后面的1为下次开始匹对的位置。
1234235612356
6后面的1是在子串中,将子串中的1对着6后面的1。
........1235
再从1开始从左至右匹对,匹配上了。
*/
#include<stdio.h>
int _strlen(char *s)
{
char *p=s;
while (*p++) NULL;
return p-s-1;
}
char *_strstr(char *s1, char *s2)
{
if (!*s1 || !*s2)
return NULL;
char *p;
int len1 = _strlen(s1);
int len2 = _strlen(s2);
int chars2[256]= {0};
int i, j;
for (i=1; i<=len2; i++)
chars2[(unsigned char)s2[i-1]] = i; //子串各字符码对应的序号,相同字符取最右边的序号。
i = 0;
while (i<=len1-len2)
{
j = 0;
while (j < len2)
{
if (s1[i] == s2[j])
//匹对时
{
i++;
//继续下一字符匹对
j++;
}
else
//不匹对时
{
p = s1 + i + len2 - j;
//看看跟着子串尾的字符
if (chars2[(unsigned char)*p] == 0)
//如果不在子串中
i = p - s1 + 1;
//下一个字符为下次开始匹对的位置。
else
i = p - (chars2[(unsigned char)*p]-1) - s1; //在子串中时,将其对着模式串的字符,
//子串第一个字符对应的位置为下次开始匹对的位置。
break;
}
}
if (j == len2)
//匹配时
return s1+i-len2;
//返回匹配串首地址
}
return NULL;
//没匹配上返回NULL
}
main()
{
char s1[]="12342356123561235", s2[]="1235", *p;
int count=0;
int len=_strlen(s2);
printf("模式串 %s
子串 %s\n", s1, s2);
for (p=_strstr(s1,s2); p; p=_strstr(++p,s2))
{
count++;
printf("%.*s %s\n", len, p, p);
}
printf("%d个匹配\n", count);
}
[此贴子已经被作者于2016-12-12 06:24编辑过]