String Matching
Input
The input consists of several test cases. Each test case consists of two lines, first a non-emptypattern, then a non-emptytext. Input is terminated by end-of-file. The input file will not be larger than 5 Mb.
Output
For each test case, output one line containing the positions of all the occurences ofpatternintext, from first to last, separated by a single space.
Sample Input 1 | Sample Output 1 |
---|---|
|
|
题意
多组输入,每组两行,模式串和对比串,输出上面的模式串在下面的字符串中的所有位置下标,下标从0开始
思路1
KMP算法,套个模版就可以了
思路2
用string的find,str2.find(str1,x),关于这个函数的用法http://www.cplusplus.com/reference/string/string/find/
代码1
#include<stdio.h>
#include<string.h>
using namespace std;
int const MAXM = 4000000;
char s[MAXM], t[MAXM];
int next[MAXM], n;
int shuchu[MAXM];
void get_next()
{
next[0] = -1;
int i = 0, j = -1;
while (t[i] != '\0')
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int KMP()
{
get_next();
int i = 0, j = 0, ans = 0, len = strlen(t);
while (s[i])
{
if (j == -1 || s[i] == t[j])
{
i++;
j++;
}
else
j = next[j];
if (j == len)
{
j = next[j];
shuchu[ans++] = i;
}
}
return ans;
}
int main()
{
while (gets(t)) {
gets(s);
int ss = KMP();
for (int i = 0; i < ss; i++)
{
if (i)printf(" ");
printf("%d", shuchu[i]-strlen(t));
}
puts("");
}
}
代码2
#include<bits/stdc++.h>
using namespace std;
int main(){
string str1,str2;
int cnt[100000];
while(getline(cin,str1)){
getline(cin,str2);
int pos=0,x=0;
while(str2.find(str1,x)!=-1&&x<str2.size()){
cnt[pos++]=str2.find(str1,x);
x=cnt[pos-1]+1;
}
for(int i=0;i<pos;i++){
printf("%d%c",cnt[i],i==pos-1?'\n':' ');
}
}
return 0;
}
原文链接: https://www.cnblogs.com/zhien-aa/p/6284119.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/247676
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!