Pagini recente » Cod sursa (job #1203505) | Cod sursa (job #2341901) | Cod sursa (job #667423) | Cod sursa (job #3160162) | Cod sursa (job #2163961)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int nx=2000002;
char N[nx],M[nx];
int pref[nx];
void Prefix(char N[])
{
int n=strlen(N);
int k=0;
for(int i=1; i<n; i++)
{
while(N[i]!=N[k] && k>0)
k=pref[k-1];
if(N[i]==N[k])
k++;
pref[i]=k;
}
}
vector < int > v;
void kmp (char N[], char M[])
{
Prefix(N);
int k=0;
int x=strlen(M);
int y=strlen(N);
for(int i=0; i<x; i++)
{
while(N[k]!=M[i] && k>0)
k=pref[k-1];
if(N[k]==M[i])
k++;
if(k==y)
v.push_back(i-k+1);
}
}
int main()
{
in>>N>>M;
kmp(N,M);
out<<v.size()<<'\n';
for(int i=0; i<min((int)v.size(),1000); i++)
out<<v.at(i)<<' ';
return 0;
}