Pagini recente » Cod sursa (job #806969) | Cod sursa (job #3222642) | Cod sursa (job #2775637) | Cod sursa (job #1982035) | Cod sursa (job #617860)
Cod sursa(job #617860)
#include <cstdio>
#include <fstream>
using namespace std;
const int NMAX = 2000005;
const char in[] = "strmatch.in";
const char out[] = "strmatch.out";
int urm[NMAX],m,n;
int matches[1005];
char T[NMAX],P[NMAX];
ifstream fin(in);
ofstream fout(out);
void urmatorul(char *p)
{
int k=-1,x;
urm[0] = 0;
for(x=1; x<m; x++)
{
while(k>0 && p[k+1] != p[x]) k = urm[k];
if(p[k+1] == p[x])
k++;
urm[x] = k + 1;
}
}
/*
void urmatorul2(char *p)
{
int i = 1;
int j = 0;
urm[0] = 0;
while(i < m)
{
if(p[j] == p[i])
{
urm[i] = j+1;
i++;
j++;
}
else
if(j > 0)
j = urm[j-1];
else
{
urm[i] = 0;
i++;
}
}
for(i=0; i<m; i++)
printf("%d ",urm[i]);
}
void make_prefix(char *A)
{
int i, q = 0;
for (i = 2, urm[1] = 0; i < m; ++i)
{
while (q && A[q+1] != A[i])
q = urm[q];
if (A[q+1] == A[i])
++q;
urm[i] = q;
}
for(i=1; i<m; i++)
printf("%d ",urm[i]);
}
*/
int main()
{
fin.get(P,NMAX,'\n');
fin.get();
fin.get(T,NMAX,'\n');
fin.get();
m = strlen(P);
n = strlen(T);
urmatorul(P);
int i , x = -1, matchesCount = 0;
for(i=0; i<n; i++)
{
while(x>0 && P[x+1] != T[i]) x = urm[x];
if(P[x+1] == T[i]) x++;
if(x == m-1)
{
if(matchesCount < 1000)
matches[++matchesCount] = i-m+1;
x = urm[x];
}
}
fout<<matchesCount<<'\n';
for(i=1; i<=matchesCount; i++)
fout<<matches[i]<<" ";
fout<<'\n';
fin.close();
fout.close();
return 0;
}