Pagini recente » Cod sursa (job #2965238) | Cod sursa (job #3284995) | Cod sursa (job #3177926) | Cod sursa (job #1525759) | Cod sursa (job #3216827)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
char a[NMAX], b[NMAX];
int p[NMAX];
vector<int> rasp;
int main()
{
fin >> (a+1);
fin >> (b+1);
int n = strlen(a+1);
int m = strlen(b+1);
p[1] = 0;
for(int i=2;i<=n;i++){
int curr_match = p[i];
while(a[i] != a[curr_match + 1] and curr_match != 0){
curr_match = p[curr_match];
}
if(a[i] == a[curr_match + 1]) p[i] = curr_match + 1;
else p[i] = 0;
}
int ind = 0;
for(int i=1;i<=m;i++){
while(b[i] != a[ind + 1] and ind != 0){
ind = p[ind];
}
if(b[i] == a[ind+1]) ind++;
if(ind == n){
rasp.push_back(i-n);
ind = p[ind];
}
}
fout << rasp.size() << '\n';
for(auto it: rasp){
fout << it << ' ';
}
return 0;
}