Pagini recente » Cod sursa (job #732595) | Cod sursa (job #2589675) | Cod sursa (job #2386775) | Cod sursa (job #2669216) | Cod sursa (job #1958114)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,j,k,l,r,z[4000002],zprev,nr;
char s[4000002];
int main()
{
f.getline(s+1,2000002);
m=strlen(s+1);
f.getline(s+strlen(s+1)+1,2000002);
n=strlen(s+1);
l=r=1;
for(i=1;i<=n;i++)
{
if(i>r)
{
j=i;
while(j<=n && s[j]==s[j-i+1]) j++, z[i]++;
l=i; r=j-1;
}
else
{
zprev=z[i-l+1];
if(zprev>=r-i+1)
{
z[i]=r-i+1;
j=r+1;
while(j<=n && s[j]==s[j-i+1]) j++, z[i]++;
r=j-1; l=i;
}
else
{
z[i]=zprev;
}
}
}
for(i=m+1;i<=n;i++) if(z[i]>=m) nr++;
g<<nr<<'\n';
if(nr>1000) nr=1000;
for(i=m+1;i<=n && nr;i++)
{
if(z[i]>=m) g<<i-m-1<<' ', nr--;
}
return 0;
}