Esempio C:
codice:
#include <stdio.h>
#include <string.h>
#include <malloc.h>
void preKmp(char *x, int m, int kmpNext[])
{
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m)
{
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
int KMP(char *x, char *y)
{
int m,n;
int i, j;
int *kmpNext;
m = strlen(x);
n = strlen(y);
kmpNext = (int*)malloc(sizeof(int)*m);
if ( !kmpNext )
{
printf("Memoria insufficiente.\n");
return - 1;
}
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m)
{
//OUTPUT(j - i);
free(kmpNext);
return j - i;
//i = kmpNext[i];
}
}
free(kmpNext);
return -1;;
}
int main()
{
int res;
char *x = "stringa";
//char *x = "ciao";
char *y = "questa e' la stringa di prova";
res = KMP(x, y);
if ( res >= 0 )
printf("stringa '%s' trovata in posizione %d\n", x, res);
else
printf("\nStringa '%s' non trovata.\n", x);
return 0;
}
Esempio C#:
codice:
using System;
namespace KnuthMorrisPratt
{
class Program
{
static void Main(string[] args)
{
string x = "stringa";
//string x = "ciao";
string y = "questa e' la stringa di prova";
int res = KMP(x, y);
if (res >= 0)
Console.WriteLine("stringa '{0}' trovata in posizione {1}", x, res);
else
Console.WriteLine("Stringa '{0}' non trovata.", x);
}
static void preKmp(string x, int m, int[] kmpNext)
{
int i = 0;
int j = kmpNext[0] = -1;
while (i < m - 1)
{
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
static int KMP(string x, string y)
{
int m,n;
int i, j;
m = x.Length;
n = y.Length;
int[] kmpNext = new int[m];
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m)
{
//OUTPUT(j - i);
return j - i;
//i = kmpNext[i];
}
}
return -1;
}
}
}