Pagini recente » Cod sursa (job #333584) | Cod sursa (job #321130) | Cod sursa (job #42503) | Cod sursa (job #1593321) | Cod sursa (job #1970741)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string F,S;
int PRE[2000005];
int ns,nf;
void ff(){
int i=1,len=0;
while(i<=nf){
if(F[i]==F[len]){
len++;
PRE[i]=len;
i++;
}
else{
if(len!=0)
len=PRE[len-1];
else{
PRE[i]=len;
i++;
}
}
}
}
int r;
vector<int> SOL;
void kmp(){
int i=0,j=0;
while(i<=ns){
if(S[i]==F[j]){
i++;
j++;
}
if(j==nf){
r++;
if(r<=1000){
SOL.push_back(i-j);
}
j=PRE[j-1];
}
if(i<=ns&&S[i]!=F[j]){
if(j!=0)
j=PRE[j-1];
else i++;
}
}
}
void solve(){
ff();
kmp();
out<<r<<"\n";
for(auto x : SOL){
out<<x<<" ";
}
}
int main(){
in>>F>>S;
nf=F.size();
ns=S.size();
solve();
return 0;
}