Pagini recente » Cod sursa (job #2751278) | Cod sursa (job #2050703) | Cod sursa (job #1851104) | Cod sursa (job #1147948) | Cod sursa (job #2574774)
#include <fstream>
#include <cstring>
#include <vector>
#define MaxLG 2000005
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int Next[MaxLG], N, M;
char str1[MaxLG], str2[MaxLG];
vector <int> Answer;
void next()
{
int k = -1, x;
for(x = 1; x < M; x++){
while(k > 0 && str2[k + 1] != str2[x]){
k = Next[x];
}
if(str2[k + 1] == str2[x]){
++k;
}
Next[x] = k;
}
}
int main()
{
int x = -1;
cin.getline(str2,MaxLG);
cin.getline(str1,MaxLG);
N = strlen(str1);
M = strlen(str2);
next();
for(int i = 0; i < N; i++){
while(x > 0 && str2[x + 1] != str1[i]){
x = Next[x];
}
if(str2[x + 1] == str1[i]){
x++;
}
if(x == M - 1){
Answer.push_back(i - M + 1);
}
}
cout << Answer.size() << "\n";
for(int i = 0; i < Answer.size(); i++){
cout << Answer[i] << " ";
}
return 0;
}