Answer to Question #328865 in Python for kalpana T

Question

Problem : Implement the Knuth-Morris-Pratt algorithm for pattern matching. Search for all occurrences of

a pattern P in a text T.

Input Format: The input text file specifies the pattern P and the text T. The first line of the input file is the

pattern P and the second line specifies the text T. Assume that all characters in the pattern and text are from

the English alphabet and are lower case.

Output Format: Print out the index of every position in the text T where the pattern P occurs. Assume that the

pattern and text have than 10000 characters.

Sample Input 1:

abab

cababbababcbccba

Sample Output 1:

1 6

Sample Input 2:

abab

cabbbbabaacbccba

Sample Output 2:

Pattern not found.

Answer 1

import os

f1 = open("input.txt", "r")
T = open("temp.txt", "w")
char = ''
while char != '\n':
    char = f1.read(1)
    print(char,end='')
while 1:
    char = f1.read(1)
    if not char:
        break
    T.write(char)
    print(char,end='')
print()
T.close()
T = open("temp.txt", "r")
f1.seek(0)
charT = ''
i = -1
flag = 0
while 1:
    charT = T.read(1)
    if not charT:
        break    
    i += 1
    char = f1.read(1)
    while charT != char:
        charT = T.read(1)
        if not charT:
            break
        i += 1
    if not charT:
        break
    if charT == char:
        pos = i
        while (charT == char):
            charT = T.read(1)
            char = f1.read(1)
            if not charT:
                break                            
            i += 1
        if char == '\n':
            flag = 1
            f1.seek(0)
            print(pos, end=' ')
        else:
            f1.seek(0)
if flag == 0:
    print('\nPattern not found.')
f1.close()
T.close()
os.remove("temp.txt")