Pagini recente » Istoria paginii runda/rar13 | Diferente pentru info-oltenia-2018/individual/clasament/11-12 intre reviziile 4 si 3 | Cod sursa (job #1031567) | Cod sursa (job #295053) | Cod sursa (job #2201104)
#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 Make_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 Match_KMP (char N[], char M[])
{
Make_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;
Match_KMP(N,M);
out<<v.size()<<'\n';
for(int i=0; i<min((int)v.size(),1000); i++)
out<<v.at(i)<<' ';
return 0;
}