Pagini recente » Cod sursa (job #1435769) | Cod sursa (job #434096) | Cod sursa (job #2386263) | Cod sursa (job #1234237) | Cod sursa (job #750671)
Cod sursa(job #750671)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define TEST 0
void open_file(){
if(TEST)
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
} else
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
}
}
char a[2000002],b[2000002];
int u[2000002],n,nr;
vector<int>v;
void prefix(){
int i,k=-1;
u[0]=-1;
n = strlen(a);
for(int i=1;i<n;i++)
{
while(k>-1 && a[k+1] != a[i])k=u[k];
if(a[k+1] == a[i])k++;
u[i]=k;
}
}
void kmp(){
int i,k=-1,m;
m = strlen(b);
for(i=0;i<m;i++)
{
while(k>-1 && a[k+1] != b[i])k=u[k];
if(a[k+1] == b[i])k++;
if(k == n - 1)
{
nr++;
if(nr < 1000) v.push_back( i-k );
k=u[k];
}
}
}
int main(){
open_file();
scanf("%s ",a);
scanf("%s ",b);
prefix();
kmp();
//for(int i=0;i<n;i++)printf("%d ",u[i]);
printf("%d\n",nr);
for(int i=0;i<v.size();i++)printf("%d ",v[i]);
return 0;
}