Pagini recente » Cod sursa (job #419713) | Cod sursa (job #255344) | Cod sursa (job #622981) | Cod sursa (job #3180149) | Cod sursa (job #617890)
Cod sursa(job #617890)
#include <cstdio>
#include <fstream>
#include <cstring>
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 ;
}
}*/
void urmatorul(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]);
}
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;
}