是看了LZL大佬的博客才学到的一种新查找方式,感觉还挺好用的.就记录下来
作用是：在一个文本串中查找子串是否存在或者组成字符的最近位置,这个子串的特点是由文本串中的字符按照从左往右的顺序截取若干个得到的
这就是不能用kmp算法的地方, 因为kmp算法适用于 模式串是由文本串中连续的若干字符组成 的查找
序列自动机里用到了next二维数组, next[][],储存着在i位置之后最近的j字符的位置在哪儿.
例如next[5][2] = x: 首先2是由 ‘c‘ - ‘a‘得到的,所以代表着c字符在5位置之后的最近位置x
需要注意的一点是文本串需要预留出一个0位置的空间出来作为起点,所以输入变为
scanf("%s", str + 1);//这样就预留出了0位置
获得next数组的操作以及注解
void getnext()
{
memset(next, 0, sizeof(next));//初始化为0代表i位置之后没有该字符
int len = strlen(str + 1);//长度相应的从1下标开始
for(int i = len; i >= 1; i --)
{
for(int j = 0; j < 26; j ++)
{
next[i - 1][j] = next[i][j];//str i-1位置继承str i位置的离其它字符最近的位置是第几个
}
next[i - 1][str[i] - ‘a‘] = i;// str i-1位置离str[i]字符的最近位置变为第i个.
}
}
查找部分代码
int flag = 1;
scanf("%s", s);
int len = strlen(s);//模式串长度
int now = 0;//起点0记录了所有字符的最近位置,从0开始找
for(int i = 0; i < len; i ++)
{
now = next[now][s[i] - ‘a‘];
if(!now)//如果查到某个字符结果为0说明now位置之后不再有该字符,标记跳出
{
flag = 0;
break;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
例题在此：https://ac.nowcoder.com/acm/contest/392/J
AC完整代码
#include<stdio.h>
#include<string.h>
char str[1000000 + 10];
char s[1000000 + 10];
int next[1000000 + 10][30];
void getnext()
{
memset(next, 0, sizeof(next));//初始化为0代表i位置之后没有该字符
int len = strlen(str + 1);//长度相应的从1下标开始
for(int i = len; i >= 1; i --)
{
for(int j = 0; j < 26; j ++)
{
next[i - 1][j] = next[i][j];//str i-1位置继承str i位置的离其它字符最近的位置是第几个
}
next[i - 1][str[i] - ‘a‘] = i;// str i-1位置离str[i]字符的最近位置变为第i个.
}
}
int main()
{
scanf("%s", str + 1);
getnext(); //获得序列自动机的next数组
int T;
scanf("%d", &T);
getchar();
while(T --)
{
int flag = 1;
scanf("%s", s);
int len = strlen(s);//模式串长度
int now = 0;//起点0记录了所有字符的最近位置,从0开始找
for(int i = 0; i < len; i ++)
{
now = next[now][s[i] - ‘a‘];
if(!now)//如果查到某个字符结果为0说明now位置之后不再有该字符,标记跳出
{
flag = 0;
break;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
原文：https://www.cnblogs.com/yuanweidao/p/10752497.html