Pagini recente » Cod sursa (job #1061530) | Cod sursa (job #2560855) | Cod sursa (job #2229336) | Cod sursa (job #1904604) | Cod sursa (job #761588)
Cod sursa(job #761588)
#include<fstream>
#include<string.h>
#define nmax 2000008
#define min(a,b) (a>b ? b :a)
#define mmax 2000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N, M;
char p[nmax], T[nmax];
int next[nmax], pos[1005];
void prefix ()
{
int k = -1;
for(int i = 2; i <= N; i++)
{
while(k && p[k+1] != p[i])
k = next[k];
if(p[k+1] == p[i])
++k;
next[i] = k;
}
}
void det_ap()
{
int k = 0, nr = 0;
for(int i = 1 ;i <= M ;i++)
{
while(k && p[k+1] != T[i])
k = next[k];
if(p[k+1] == T[i] )
++k;
if(k == N)
{
k = next[N];
++nr;
if(nr <=1000 )
pos[nr] = i - N ;
}
}
fout <<nr <<'\n';
for(int i = 1; i <= min(nr, 1000); i++)
fout <<pos[i] <<" ";
}
void read()
{
fin.get(p + 1,nmax, '\n');
N = strlen(p + 1);
fin.get();
fin.get(T + 1,nmax, '\n');
M =strlen(T + 1);
prefix();
}
int main()
{
read();
det_ap();
fin.close();
return 0;
}