Pagini recente » Cod sursa (job #1612433) | Cod sursa (job #1582379) | Cod sursa (job #1994324) | Cod sursa (job #539730) | Cod sursa (job #2090909)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[2000001],d[2000001],n,m;
char s[2000001],v[2000001];
void prefix()
{
int k;
k=-1;
pi[0]=-1;
for(int i=1;i<=n;i++)
{
while(k>-1&&s[k+1]!=s[i])
k=pi[k];
if(s[k+1]==s[i])
k++;
pi[i]=k;
}
}
int main()
{
int k,nr=0;
f>>s>>v;
m=strlen(v);
n=strlen(s)-1;
prefix();
k=-1;
d[0]=k;
for(int i=1;i<m;i++)
{
while(k>-1&&v[i]!=s[k+1])
k=pi[k];
if(v[i]==s[k+1])
k++;
d[i]=k;
}
for(int i=n;i<m;i++)
{
if(d[i]==n)
nr++;
}
g<<nr<<endl;
nr=0;
for(int i=n;i<m;i++)
{
if(d[i]==n)
{
if(nr<=1000)
{g<<i-n<<" ";
nr++;
}
else
break;
}
}
f.close();
g.close();
return 0;
}