Pagini recente » Cod sursa (job #1601026) | Cod sursa (job #1301774) | Cod sursa (job #694078) | Cod sursa (job #2084359) | Cod sursa (job #2532917)
def solve(n, m, a, b):
ans = []
""" a appears in b
pos[i] = how many characters match the suffix of a[:i + 1] with the prefix of a[1:]
"""
pos = [0 for _ in range(n + 1)]
pos[1] = 0
k = 0
for i in range(2, n + 1):
while k != 0 and a[k + 1] != a[i]:
k = pos[k]
if a[k + 1] == a[i]:
k += 1
pos[i] = k
k = 0
for i in range(1, m + 1):
while k != 0 and a[k + 1] != b[i]:
k = pos[k]
if a[k + 1] == b[i]:
k += 1
if k == n:
ans.append(i - n + 1 - 1)
k = pos[k]
return ans
if __name__ == "__main__":
with open('strmatch.in', 'rt') as fin:
a = 'a' + next(fin).strip()
b = 'a' + next(fin).strip()
n, m = len(a) - 1, len(b) - 1
ans = solve(n, m, a, b)
with open("strmatch.out", 'wt') as fout:
fout.write('{}\n'.format(len(ans)))
for v in ans[:1000]:
fout.write('{} '.format(v))
fout.write('\n')