Pagini recente » Cod sursa (job #2177912) | Cod sursa (job #590776) | Cod sursa (job #1220336) | Cod sursa (job #63082) | Cod sursa (job #1203870)
#include <fstream>
#include <cstring>
using namespace std;
char a[4000005],b[2000005];
int n,m,z[4000005];
int main()
{
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
in>>a;
in>>b;
n=strlen(a);
m=strlen(b);
a[n]='#'; int j=0;
for (int i=n+1;i<=n+m;++i) a[i]=b[j],++j;
m=n+m+1; a[m]='\0';
int st=0,dr=0,sol=0;
for (int i=1;i<m;++i)
{
if (i<=dr)
{
z[i]=z[i-st];
if (z[i]>dr-i+1) z[i]=dr-i+1;
}
while (i+z[i]<m && a[i+z[i]]==a[z[i]]) ++z[i];
if (dr<i+z[i]-1) dr=i+z[i]-1,st=i;
if (z[i]==n) ++sol;
}
out<<sol<<"\n";
int sol2=0;
for (int i=n+1;i<m && sol2<1000;++i) if (z[i]==n) out<<i-n-1<<" ",sol2++;
in.close();
out.close();
return 0;
}