Pagini recente » Cod sursa (job #54923) | Cod sursa (job #459342) | Cod sursa (job #220234) | Cod sursa (job #2708119) | Cod sursa (job #3195113)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
int tabel[2000005];
int poz[1001];
int n,m;
int i,j,k;
int ans;
vector <int> res;
int main()
{
fin>>a>>b;
n=strlen(a); m=strlen(b);
i=1;
while(i<n){
if(a[i]==a[k]){
k++;
tabel[i]=k;
i++;
}
else if(k!=0){
k=tabel[k-1];
}
else{
tabel[i]=0;
i++;
}
}
i=0;
k=0;
while(i<m){
if(b[i]==a[k]){
k++;
i++;
if(k==n){
ans++;
if(ans<=1000){
res.push_back(i-n);
}
k=tabel[k-1];
}
}
else if(b[i]!=a[k]){
if(k!=0){
k=tabel[k-1];
}
else i++;
}
}
fout<<ans<<'\n';
for(auto x : res){
fout<<x<<' ';
}
return 0;
}