Pagini recente » Cod sursa (job #1646791) | Cod sursa (job #839704) | Cod sursa (job #572686) | Cod sursa (job #796226) | Cod sursa (job #2650228)
def get_lps(pat)->int:
i = 0
j = 1
lps = [0] * len(pat)
while j < len(pat):
if pat[i] == pat[j]:
lps[j] = i + 1
i += 1
j += 1
else:
if i != 0:
i = lps[i-1]
else:
lps[j] = 0
j += 1
return lps
def kmp(string, substring, start_index=0):
lps = get_lps(substring)
i, j = start_index, 0
while i < len(string) and j < len(substring):
if substring[j] == string[i]:
i += 1
j += 1
else:
if j == 0:
i += 1
else:
j = lps[j-1]
return i - len(substring) if j == len(substring) else -1
with open('strmatch.in', 'r') as fin:
substring = fin.readline().rstrip('\n')
string = fin.readline().rstrip('\n')
index = kmp(string, substring)
results = []
with open('strmatch.out', 'w') as fout:
while index != -1 and len(results) < 1000:
results.append(index)
index = kmp(string, substring, index+1)
fout.write(str(len(results)) + '\n')
fout.write(' '.join(map(str,results)))