Pagini recente » Borderou de evaluare (job #386937) | Borderou de evaluare (job #2693977) | Cod sursa (job #2247904) | Cod sursa (job #2670905) | Cod sursa (job #2650251)
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):
lps = get_lps(substring)
i, j = 0, 0
while i < len(string):
if string[i] == substring[j]:
i += 1
j += 1
if j == len(substring):
yield i - j
j = lps[j-1]
elif i < len(string) and string[i] != substring[j]:
if j != 0:
j = lps[j-1]
else:
i += 1
yield -1
with open('strmatch.in', 'r') as fin:
substring = fin.readline().rstrip('\n')
string = fin.readline().rstrip('\n')
gen = kmp(string, substring)
index = next(gen)
matches = 0
results = []
with open('strmatch.out', 'w') as fout:
while index != -1:
matches += 1
if len(results) < 1000:
results.append(index)
index = next(gen)
fout.write(str(matches) + '\n')
for result in results:
fout.write(str(result) + ' ')