Pagini recente » Cod sursa (job #2108479) | Cod sursa (job #1608111) | Cod sursa (job #1315362) | Cod sursa (job #1562137) | Cod sursa (job #2352233)
#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;
string A,B;
vector <int> P;
int Pa[MAXN];
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>A>>B;
for(int i=1;i<A.size();i++){
if(A[i]==A[0]){
int j=0;
while(i+j<A.size() && A[i+j]==A[j]){
Pa[i+j]=++j;
}
i+=j;
}
}
int j=0;
for(int i=0;i<B.size();i++){
int m=0,ind=-1;
if(A[0]==B[i]){
while(j<A.size() && i+j<B.size() && A[j]==B[i+j]){
if(m<Pa[j]){
m=Pa[j];
ind=j;
}
j++;
}
if(j==A.size())P.push_back(i);
if(j>0 && ind!=-1){
j=Pa[ind]-1;
i+=ind;
}else{
i+=j;
j=0;
}
}
}
cout<<P.size()<<'\n';
for(int i=0;i<P.size();i++)cout<<P[i]<<' ';
}