Pagini recente » Cod sursa (job #2803292) | Cod sursa (job #121205) | Cod sursa (job #1913644) | Cod sursa (job #268611) | Cod sursa (job #428334)
Cod sursa(job #428334)
# include <fstream>
# include <algorithm>
# include <iostream>
# include <cstring>
# define DIM 2000002
# define NMAX 2000
using namespace std;
char a[DIM], b[DIM];
int n, m, N, urm[DIM], p[DIM];
ofstream fout ("strmatch.out");
void read ()
{
ifstream fin ("strmatch.in");
fin.getline(a, DIM);
fin.getline(b, DIM);
m=strlen(a);
n=strlen(b);
}
void urmatorul ()
{
int k=-1;
urm[0]=0;
for(int i=1;i<m;i++)
{
while (k>0 && a[k+1]!=a[i])k=urm[k];
if (a[k+1]==a[i])++k;
urm[i]=k;
}
}
void potrivire ()
{
int x=-1;
for (int i=0;i<n && N<NMAX;++i)
{
while (x>0 && a[x+1]!=b[i])x=urm[x];
if (a[x+1]==b[i])++x;
if (x==m-1)
{
p[++N]=i-m+1;
x=urm[x];
}
}
}
void afisare ()
{
fout<<N<<endl;
int M;
// sort(p+1, p+N+1);
M=N;
if (N>1000)
M=1000;
for (int i=1;i<=M;i++)
fout<<p[i]<<" ";
}
int main ()
{
read ();
if (m>n)
{
fout<<"0\n";
return 0;
}
urmatorul();
potrivire ();
afisare();
return 0;
}