Pagini recente » Cod sursa (job #615849) | Cod sursa (job #1877211) | Cod sursa (job #2922677) | Cod sursa (job #1666353) | Cod sursa (job #2024594)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int n1,n2,i,j,c[2000010], sol[1010];
void make_prefix()
{
int i,j;
j=0;
for (i=2;i<=n1;i++)
{
while (j && a[i]!=a[j]) j=c[j];
if (a[i]==a[j+1])
{
c[i]=j+1;
j++;
}
}
}
int main()
{
int i,j;
int nrsol=0;
f.getline (a,2000010);
n1=strlen(a);
f.getline (b,2000010);
n2=strlen (b);
for (i=n1;i>=1;i--)
a[i]=a[i-1];
for (i=n2;i>=1;i--)
b[i]=b[i-1];
a[0]=' ';
b[0]=' ';
make_prefix();
i=0;
for (j=1;j<=n2;j++)
{
while (a[i+1]!=b[j] && i)
{
i=c[i];
}
if (a[i+1]==b[j])
{
i++;
if (i==n1)
{
i=c[i];
nrsol++;
if (nrsol<=1000) sol[nrsol]=j-n1;
}
}
}
g<<nrsol<<"\n";
nrsol=min(nrsol,1000);
for (i=1;i<=nrsol;i++) g<<sol[i]<<" ";
return 0;
}