Pagini recente » Cod sursa (job #2167277) | Cod sursa (job #429353) | Cod sursa (job #2494245) | Cod sursa (job #2495043) | Cod sursa (job #625153)
Cod sursa(job #625153)
#include <cstdio>
#include <cstring>
#define MAX 2000005
using namespace std;
int n, m;
int p[MAX]; // sirul prefixelor (p[i] = j in prefixul de lung i, j este lungimeA celui mai mare prefix si totodata si sufix)
int d = -1; // p[1..m]
char T[MAX], P[MAX]; // sirul T[0..n-1] in care se cauta si pattern-ul P[0..m-1]
int sol[1001];
void Citeste();
void Afiseaza();
void Prefix();
void KMP();
FILE *fi, *fo = fopen("strmatch.out","w");
int main()
{
Citeste();
KMP();
//Afiseaza();
return 0;
}
void Prefix()
{
int i, k;
p[1] = 0; k = 0;
for (i = 1; i < m; i++)
{
while ( k > 0 && P[k] != P[i] )
k = p[k];
if ( P[k] == P[i] ) k++;
p[i+1] = k;
}
}
void DEBUG()
{
for ( int i = 1; i <= m; i++ )
fprintf(fo, "%d ", p[i]);
fprintf(fo, "\n");
}
void KMP()
{
Prefix();
//DEBUG();
int i, j = 0,solCount = 0;
for (i = 0; i < n; i++)
{
while ( j > 0 && P[j] != T[i] ) // j > 0 nu exista poz 0 in p[]
j = p[j];
if ( P[j] == T[i] ) j++;
if ( j == m )
{
if(solCount < 1000)
sol[++solCount] = i - m + 1;
}
}
fprintf(fo,"%d\n",solCount);
for(i=1; i<=solCount; i++)
fprintf(fo,"%d ",sol[i]);
fprintf(fo,"%c",'\n');
}
void Citeste()
{
fi = fopen("strmatch.in","r");
fscanf(fi," %s", P);
fscanf(fi, "%s", T);
n = strlen(T);
m = strlen(P);
fclose(fi);
}
void Afiseaza()
{
fprintf(fo, "%d", d);
fclose(fo);
}