引入
字符串有一种基本的操作, 叫做查找. 当你在淘宝上搜索时, 就是在查找; 当你在百度上搜索时, 也是在查找; 当你在点子字典上输入一个英文单词的时候, 也是在查找.
在 C++ 的 string 库中有一个查找的函数, 即 str1.find(str2). 其中, str1 指的是被查找的母串, str2 指的是要查找的子串. 例如下面一段程序
- string str1="Hello World";
- string str2="Hel";
- printf("%d", str1.find(str2));
这个程序的返回值是 0. 也就是说, str1.find(str2)返回的是 str2 在 str1 中第一次出现的位置.
注意事项
在开始之前, 我们约定一下几个事项:
母串表示被查找的字符串, 用 strmo 表示
子串表示要查找的字符串, 用 strch 表示
我们用 i 来表示 strmo 中的第 i 个字符, 用 j 来表示 strch 中的第 j 个字符, 使读者更容易理解.
古老的字符串查找方法
暴力的字符串查找方法就是直接模拟人的思想, 不断地在母串中一个字符一个字符地查看与子串是否匹配, 直到匹配成功或母串结束为止.
- find(String strmo, String strch)
- {
- int M=strmo.length();
- int N=strch.length();
- for(int i=0;i<=N-M;i++)
- {
- int temp;
- for(j=0;j<M;j++)
- if(strch[i+j] != strmo[j])
- {
- temp=j;
- break;
- }
- if(j == M)
- return i;
- }
- }
很明显, 这个算法的复杂度为 O(NM)
- dfa[strch[0]][0] = 1;
- for(int X=0,j=1;j<M;j++)
- {
- for(int c=0;c<R;c++)
- dfa[c][j] = dfa[c][X];
- dfa[strch[j]][j] = j+1;
- X = dfa[pat.charAt(j)][X];
- }
- void GetNext(char* strch,int next[])
- {
- int Len = strlen(strch);
- next[0] = -1;
- int k = -1;
- int j = 0;
- while (j<Len - 1)
- {
- //strch[k]表示前缀, strch[j]表示后缀
- if (k==-1 || strch[j]==strch[k])
- {
- k++;
- j++;
- next[j]=k;
- }
- else
- k=next[k];
- }
- }
- bool kmp(char *strmo,char *strch)
- {
- int i=0,j=0,len0=strlen(strmo),len1=strlen(strch);
- while(i<len1&&j<len0)
- {
- if(i==-1||strmo[i]==strch[j])
- {
- i++;
- j++;
- }
- else
- j=next[j];
- }
- return i==len1;
- }
- int kmp_len(char *strmo,char *strch){
- int i=0,j=0,maxlen=0,len0=strlen(strmo),len1=strlen(strch);
- while(i<len1&&j<len0)
- {
- if(i==-1 || strmo[i]==strch[j])
- {
- maxlen=max(++i,maxlen);
- j++;
- }
- else
- j=next[j];
- }
- return maxlen;
- }
来源: https://www.cnblogs.com/Wolfbeyond/p/9484410.html