Pagini recente » Cod sursa (job #2321041) | Cod sursa (job #1442216) | Cod sursa (job #343595) | Cod sursa (job #2823113) | Cod sursa (job #2825334)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char a[2000005];
char b[2000005];
int s[2000005];
int nr;
int n;
int m;
int rez[2000005];
int main()
{
f>>(a);
f>>(b);
int n=strlen(a);
int m=strlen(b);
--n;
--m;
int i=0;
int j=1;
s[0]=-1;
while(i<=j && j<=n)
{
if(a[i]==a[j])
{
s[j]=i;
++i;
++j;
}
else
{
--i;
while(a[i+1]!=a[j] && i!=-1)
{
i=s[i];
}
++i;
if(a[i]==a[j])
{
s[j]=i;
++i;
++j;
}
else
{
s[j]=-1;
++j;
}
}
}
i=0;
j=0;
while(i<=j && j<=m)
{
if(a[i]==b[j] && i<=n)
{
if(j!=0 && i!=0)
rez[j]=i;
else if(j==0 || i==0)
rez[j]=i;
++i;
++j;
}
else
{
--i;
while(a[i+1]!=b[j] && i!=-1)
{
i=s[i];
}
++i;
if(a[i]==b[j])
{
rez[j]=i;
++i;
++j;
}
else
{
rez[j]=-1;
++j;
}
}
if(i==n+1)
{
i=s[i-1]+1;
}
}
int cont=0;
for(int i=0;i<=m;++i)
if(rez[i]==n)
++cont;
g<<cont<<"\n";
int nr=0;
for(int i=0;i<=m;++i)
{
if(rez[i]==n && nr<1000)
{
g<<i-n<<" ";
++nr;
}
}
return 0;
}