Pagini recente » Cod sursa (job #2123345) | Cod sursa (job #1984880) | Cod sursa (job #2389646) | Rating Pentiuc Tudor (Tudor0998) | Cod sursa (job #687419)
Cod sursa(job #687419)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
char a[2000001],b[2000001],n,m;
int v[2000001],poz[1001];
void prefix()
{
int i,q;
q=0;
v[1]=0;
for(i=2;i<=n;i++) {
while((q)&&(a[i]!=a[q+1]))
q=v[q];
if(a[i]==a[q+1])
q++;
v[i]=q;
}
}
int main ()
{
int i,p,q;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
f.close();
n=strlen(a);
m=strlen(b);
for(i=n;i>=0;i--)
a[i]=a[i-1];
a[0]=' ';
for(i=m;i>=0;i--)
b[i]=b[i-1];
b[0]=' ';
prefix();
p=0;
q=0;
for(i=1;i<=m;i++) {
while((q)&&(b[i]!=a[q+1]))
q=v[q];
if(b[i]==a[q+1])
q++;
if(q==n) {
q=v[n];
p++;
if(p<1000)
poz[p]=i-n;
}
}
g<<p<<'\n';
if(p>1000)
p=1000;
for(i=1;i<=p;i++)
g<<poz[i]<<" ";
g.close();
return 0;
}