Pagini recente » Cod sursa (job #3150651) | Cod sursa (job #1925234) | Cod sursa (job #1133700) | Cod sursa (job #1295117) | Cod sursa (job #2024597)
#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;
c[1]=0;
for (i=2;i<=n1;i++)
{
while (j && a[i]!=a[j+1]) 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();
// for (i=1;i<=n1;i++) cout<<c[i]<<" ";
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;
}