问题描述:
对于主串M和模式串P,找到P在M中出现的所有子串的第一个字符在P中的位置。P中第一个字符所在的位置为0。首行的数字表示有多少组字符串。
样例输入:
输入:
2
ababababa
ababa
aaa
aa
输出:
0 2 4
0 1
思路:
从头在m中匹配p,找到匹配的第一个字符串pos,继续从pos+1开始下一次匹配
知识点:
string
- str.find(str1), 当str1是str的子串时,返回其在str中第一次出现的位置;如果不是,返回string::npos;
- string::npos本身值为1, 可以作为find函数失配时的返回值
- str.find(str1, pos)从pos位开始匹配str1,返回值与上面相同
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
void Solve(string m, string p){
int pos = m.find(p);
int len = m.size();
printf("%d", pos);
while(len - pos - 1 >= p.size()){ //如果剩余字符串的长度不小于p的长度则继续判断
int pos1 = m.find(p, pos+1);
if(pos1 != string::npos){
printf(" %d", pos1);
pos = pos1;
}
else
break;
}
printf("\n");
}
int main(){
string m, p;
int n;
scanf("%d%*c", &n);
while(n--){
getline(cin, m);
getline(cin, p);
Solve(m, p);
}
return 0;
}