Pagini recente » Cod sursa (job #2376261) | Cod sursa (job #3199158) | Cod sursa (job #1530425) | Cod sursa (job #2213626) | Cod sursa (job #704037)
Cod sursa(job #704037)
#include <fstream>
#include <cstring>
using namespace std;
#define nmax 2000002
int urm[nmax];
char T[nmax], P[nmax];
int n, m, qq;
bool here[nmax];
void citire()
{
ifstream in("strmatch.in");
in>>P>>T;
n = strlen(T); m = strlen(P);
}
void afisare()
{
ofstream out("strmatch.out");
//for(int k=0; k<m; k++)
//out<<urm[k]<<" ";
out<<qq<<"\n";
if(qq > 1000)
qq = 1000;
for(int i=0; i<n && qq; i++)
if(here[i])
{
out<<i<<" ";
qq--;
}
}
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 kmp()
{
int i, x=-1;
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)
{
here[i-m+1] = true;
qq++;
//out<<i-m+1<<"\n";
x = urm[x];
}
}
}
int main()
{
citire();
urmatorul(P);
kmp();
afisare();
return 0;
}