Pagini recente » Cod sursa (job #591664) | Cod sursa (job #412098) | Cod sursa (job #1951007) | Cod sursa (job #1817168) | Cod sursa (job #977792)
Cod sursa(job #977792)
#include<stdio.h>
#include<string.h>
#include<vector>
#define NMAX 2000000
using namespace std;
vector <int> sol;
char a[NMAX+5],b[NMAX+5];
int pi[NMAX+5];
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,n,m,p;
gets(a+1); n=strlen(a+1);
gets(b+1); m=strlen(b+1);
p=0;
pi[1]=0;
for(i=2;i<=n;i++) {
while(p && a[i]!=a[p+1])
p=pi[p];
if(a[p+1]==a[i])
p++;
pi[i]=p;
}
p=0;
for(i=1;i<=m;i++) {
while(p && b[i]!=a[p+1])
p=pi[p];
if(a[p+1]==b[i])
p++;
if(p==n) {
sol.push_back(i-n);
p=pi[n];
}
}
printf("%d\n",sol.size());
for(i=0;i<sol.size() && i<1000;i++)
printf("%d ",sol[i]);
return 0;
}