Pagini recente » Clasament | Cod sursa (job #2704843) | Cod sursa (job #427851) | Cod sursa (job #381814) | Cod sursa (job #617864)
Cod sursa(job #617864)
#include <cstdio>
#include <fstream>
#include <string>
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;
}
}
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;
}