Cod sursa(job #2650246)

Utilizator vali_27Bojici Valentin vali_27 Data 17 septembrie 2020 20:08:02
Problema Potrivirea sirurilor Scor 40
Compilator py Status done
Runda Arhiva educationala Marime 1 kb
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)
	results = []
	
	with open('strmatch.out', 'w') as fout:
	
		while index != -1 and len(results) < 1000:
			results.append(index)
			index = next(gen)
		fout.write(str(len(results)) + '\n')
		for result in results:
			fout.write(str(result) + ' ')