Pagini recente » Cod sursa (job #274788) | Cod sursa (job #258321) | Cod sursa (job #2421163) | Cod sursa (job #125582) | Cod sursa (job #1617746)
#include <cstring>
#include <fstream>
#include <iostream>
#define P 73
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, s;
int na, nb,n,nr,i;
int z[4000005];
int l,r;
int main()
{
getline(fin, a);
getline(fin, b);
s=a+'#'+b;
n=s.length();
for(i=1;i<n;++i)
{
if(i>r)
{
int p1=i;
int p2=0;
while(s[p1]==s[p2])
{
++p1; ++p2;
++z[i];
}
r=p1-1;
l=i;
}
else{
if(z[i-l]<r-i+1) z[i]=z[i-l];
else {
int p1=r+1;
int p2=r-i+1;
z[i]=r-i+1;
while(s[p1]==s[p2])
{
++p1;
++p2;
++z[i];
}
r=p1-1;
l=i;
}
}
if(z[i]==a.length()) ++nr;
}
fout<<nr<<'\n';
nr=0;
int k=a.length()+1;
int k2=s.length();
int k3=a.length();
while(k<k2 && nr<1000)
{
if(z[k]==k3)
{
fout<<k-a.length()-1<<" ";
nr++;
}
++k;
}
return 0;
}