Pagini recente » Cod sursa (job #3276081) | Cod sursa (job #2652735) | Cod sursa (job #2862702) | Cod sursa (job #2657834) | Cod sursa (job #2132423)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int nx=2000002;
char a[nx],b[nx];
int prefix[nx];
void calc_pref (char a[])
{
int x=strlen(a);
int k=0;
for(int i=1; i<x; i++)
{
while(a[i]!=a[k] && k>0)
k=prefix[k-1];
if(a[i]==a[k])
k++;
prefix[i]=k;
}
}
vector < int > sol;
void kmp (char a[], char b[])
{
calc_pref(a);
int k=0;
int x=strlen(b);
for(int i=0; i<x; i++)
{
while(a[k]!=b[i] && k>0)
k=prefix[k-1];
if(a[k]==b[i])
k++;
if(k==strlen(a))
sol.push_back(i-k+1);
}
}
int main()
{
in.getline(a,nx);
in.getline(b,nx);
kmp(a,b);
out<<sol.size()<<'\n';
int x=sol.size();
for(int i=0; i<min(x,1000); i++)
out<<sol.at(i)<<' ';
return 0;
}