The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
import java.io.*;
class k_m_p_fun {
void failure(String p, int f[]) {
int i = 1;
int j = 0;
f[0] = 0;
int m = p.length();
while (i < m) {
if (p.charAt(j) == p.charAt(i)) {
f[i] = j + 1;
i++;
j++;
} else if (j > 0)
j = f[j - 1];
else {
f[i] = 0;
i++;
}
}
}
int KMP(String t, String p, int f[]) {
failure(p, f);
int i = 0;
int j = 0;
int n = t.length();
int m = p.length();
while (i < n) {
if (p.charAt(j) == t.charAt(i)) {
if (j == m - 1)
return i - m + 2;
i++;
j++;
} else if (j > 0)
j = f[j - 1];
else i++;
}
return -1;
}
}
class k_m_p {
public static void main(String args[])
throws IOException {
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader obj = new BufferedReader(input);
System.out.println("Enter the string:");
String s = obj.readLine();
System.out.println("Enter the string to be searched:");
String ts = obj.readLine();
k_m_p_fun f = new k_m_p_fun();
int u = ts.length();
int h[] = new int[u];
int n = f.KMP(s, ts, h);
if (n != -1)
System.out.println("Subsring matched at position:" + n);
else
System.out.println("No Substring match");
}
}
/*OUTPUT
Enter the string:
piitnewpanvel
Enter the string to be searched:
pan
Subsring matched at position:8
Process Exit...
*/
can you send me the kmp program for column matching
Bad implementation. Bad function/variable namings. No comments. Please don’t refer this code.