Pagini recente » Cod sursa (job #1783915) | Cod sursa (job #1129912) | Cod sursa (job #3348462) | Cod sursa (job #1333259) | Cod sursa (job #3348440)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=4e6+5;
string a, b;
int kmp[NMAX];
vector<int> sol;
int main()
{
fin>>a>>b;
kmp[0]=0;
for(int i=1;i<a.size();i++){
int j=kmp[i-1];
while(j>0 && a[i]!=a[j])
j=kmp[j-1];
kmp[i]=j;
if(a[i]==a[j])
kmp[i]++;
}
int j=0;
for(int i=0;i<b.size();i++){
while(j>0 && a[j]!=b[i]){
j=kmp[j-1];
}
if(a[j]==b[i])
j++;
if(j==a.size()){
sol.push_back(i-a.size()+1);
j=kmp[j-1];
}
}
fout<<sol.size()<<'\n';
for(int i=0;i<min(int(sol.size()), 1000);i++){
fout<<sol[i]<<" ";
}
return 0;
}