Pagini recente » Cod sursa (job #582146) | Cod sursa (job #2665264) | Cod sursa (job #1291504) | Cod sursa (job #1902207) | Cod sursa (job #1165430)
#include <algorithm>
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
const int N=2000005;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int Z[2*N], ap[1005];
int main()
{
int n, m, i, k, R, L, sol=0;
fin>>a>>b;
n=a.size();
a+=b;
m=a.size();
R=L=0;
for(i=1;i<m;i++)
{
if(i>R)
{
L=R=i;
for(;R<m&&a[R]==a[R-L];R++);
Z[i]=R-L;
R--;
}
else
{
k=i-L;
if(Z[k]<R-i+1) Z[i]=Z[k];
else
{
L=i;
for(;R<m&&a[R]==a[R-L];R++);
Z[i]=R-L;
R--;
}
}
if(i>=n&&Z[i]>=n)
{
sol++;
if(sol<=1000) ap[sol]=i-n;
}
}
fout<<sol<<"\n";
for(i=1;i<=min(sol, 1000);i++) fout<<ap[i]<<" ";
}