Cod sursa(job #2309976)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 30 decembrie 2018 13:01:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int DIM = 2e6 + 7;

int prefix[DIM];

vector <int> ind;

main()
{
	string word;
	string pattern;
	
	in >> pattern >> word;
	
	int n = word.size();
	int m = pattern.size();
	
	word = ' ' + word;
	pattern = ' ' + pattern;
	
	int k = 0;
	
	for(int i = 2; i <= m; i++)
	{
		while(k != 0 && pattern[k + 1] != pattern[i])
			k = prefix[k];
		
		if(pattern[k + 1] == pattern[i])
			k++;
		
		prefix[i] = k;
	}
	
	k = 0;
	
	int nr = 0;
	
	for(int i = 1; i <= n; i++)
	{
		while(k != 0 && pattern[k + 1] != word[i])
			k = prefix[k];
		
		if(pattern[k + 1] == word[i])
			k++;
		
		if(k == m)
		{
			k = prefix[m];
			
			nr++;
			
			if(ind.size() < 1000)
				ind.push_back(i - m);
		}
	}
	
	out << nr << '\n';
	
	for(int i : ind)
		out << i << ' ';
}