Cod sursa(job #2651499)

Utilizator filicriFilip Crisan filicri Data 22 septembrie 2020 19:10:12
Problema Potrivirea sirurilor Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.54 kb
f = open('strmatch.in', 'r')
g = open('strmatch.out', 'w')

def get_prefix(s):
	j = 0
	p = [0, 0]
	for i in range(2, len(s)):
		while j and s[j + 1] != s[i]:
			j = p[j]
		if s[j + 1] == s[i]:
			j = j + 1
		p.append(j)
	return p

a, b = f.read().splitlines()
a = '0' + a 
b = '0' + b

p = get_prefix(a)

n = 0
sol = []
j = 0
for i in range(1, len(b)):
	while j and a[j + 1] != b[i]:
		j = p[j]
	if a[j + 1] == b[i]:
		j = j + 1
	if j == len(a) - 1:
		n = n + 1
		sol.append(i - len(a) + 1)
		j = p[j]

print(n)
for num in sol:
	print(num, end=' ')