rabin karp

#include <stdio.h>
#include <string.h>
#include <math.h>
#define d 10

void rabinkarp(char pa[],char te[], int q);
int main()
{
char pa[20],te[20];
scanf("%s",pa);
scanf("%s",te);
rabinkarp(pa,te,11);

return 0;
}
void rabinkarp(char pa[],char te[], int q)
{
int m=strlen(pa);
int n=strlen(te);
int h=(int)pow(d,m-1) % q;
int p=0;
int t=0;
for(int i=0;i<m;i++)
{
p=(d*p+pa[i]) % q;
t=(d*t + te[i]) % q;
}
for(int s=0;s<=n-m;s++)
{
int i;
if(p==t)
{
for(i=0;i<m;i++)
{
if(pa[i]!=te[s+i])
break;
}
if(i==m)
{
printf("Pattern found at %d\n",s);
}
}

t=(d*(t-te[s]*h)+te[s+m]) % q;
if(t<0)
t+=q;
}
}

kmp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int* compute_next(char p[], int m) {
int *pi = (int*)malloc(m * sizeof(int));
if (pi == NULL) {
printf("Memory allocation failed\n");
return NULL;
}

pi[0] = 0;
int k = 0;

for (int i = 1; i < m; i++) {
while (k > 0 && p[k] != p[i]) {
k = pi[k - 1];
}
if (p[k] == p[i]) {
k++;
}
pi[i] = k;
}
return pi;
}

void kmp(char t[], char p[]) {
int n = strlen(t);
int m = strlen(p);

int *pi = compute_next(p, m);
if (pi == NULL) return;

int j = 0;

for (int i = 0; i < n; i++) {
while (j > 0 && p[j] != t[i]) {
j = pi[j - 1];
}
if (p[j] == t[i]) {
j++;
}
if (j == m) {
printf("Pattern found at index %d\n", i - m + 1);
j = pi[j - 1];
}
}

free(pi);
}

int main() {
char text[100], pattern[100];

printf("Enter text: ");
scanf("%s", text);

printf("Enter pattern: ");
scanf("%s", pattern);

kmp(text, pattern);

return 0;
}