Skip to content

Instantly share code, notes, and snippets.

@coderek
Last active October 17, 2017 03:18
Show Gist options
  • Save coderek/f4e761bbe672ae02748848e028b6e666 to your computer and use it in GitHub Desktop.
Save coderek/f4e761bbe672ae02748848e028b6e666 to your computer and use it in GitHub Desktop.
finding repeated string using kmp
def kmp(text, word):
wl = len(word)
jump = [0 for _ in range(wl)]
j = 0
i = 1
while i < wl:
if word[i] == word[j]:
jump[i] = j + 1
i+=1
j+=1
elif j == 0:
i += 1
else:
j = jump[j-1]
tl = len(text)
i = 0
j = 0
while i < tl:
if text[i] == word[j]:
i+=1
j+=1
if j == wl:
return True
elif j == 0:
i += 1
else:
j = jump[j-1]
return False
public static String kmp (String s) {
int len = s.length();
int[] LPS = new int[len];
int i = 1, j = 0;
LPS[0] = 0;
while(i < len) {
if(s.charAt(i) == s.charAt(j)) {
LPS[i ++] = ++ j;
} else if(j == 0) {
LPS[i ++] = 0;
} else {
j = LPS[j - 1];
}
}
int patternLen = len - LPS[len - 1];
if(patternLen != len && len % patternLen == 0) {
return s.substring(0, patternLen);
} else {
return s;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment