Pagini recente » Cod sursa (job #2734884) | Cod sursa (job #3266631) | Cod sursa (job #696377) | Cod sursa (job #3158880) | Cod sursa (job #2554669)
#include<bits/stdc++.h>
#define maxn 2000005
using namespace std;
char s1[maxn],s2[maxn];
int n,m,k,pi[maxn];
vector<int>rez;
ifstream ccin("strmatch.in");
ofstream ccout("strmatch.out");
void prefix(){
k=0;
for(int i=2; i<=n; i++){
while(k>0&&s1[k+1]!=s1[i])
k=pi[k];
if(s1[k+1]==s1[i])
k+=1;
pi[i]=k;
}
}
int main(){
ccin>>s1+1>>s2+1;
n=strlen(s1+1); m=strlen(s2+1);
prefix();
k=0;
for(int i=1; i<=m; i++){
while(k>0&&s1[k+1]!=s2[i])
k=pi[k];
if(s1[k+1]==s2[i])
k++;
if(k==n)
rez.push_back(i-n);
}
k=rez.size();
ccout<<k<<'\n';
for(int i=0; i<min(k,1000); i++)
ccout<<rez[i]<<' ';
return 0;
}