Cod sursa(job #2041700)

Utilizator Spiromanii_MessiUNIBUCThrowTerror Spiromanii_Messi Data 17 octombrie 2017 18:16:21
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std ;

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

const int MAX = 4e6 + 14 ;

char sir [MAX] ; // string concatenated

int main(int argc, char const *argv[])
{
	fin >> (sir + 1) ; 
	int patternSize = strlen (sir + 1) ;
	sir [patternSize + 1] = '#' ;
	fin >> (sir + patternSize + 1) ; 
	int totalLength = strlen (sir + 1) ;
	vector <int> pi (totalLength + 1, 0) ; 
	vector <int> sol ;
	int noSol = 0 ; 
	for (int i = 2 ; i <= totalLength ; ++ i) {
		int k = pi [i - 1] ; 
		while (k and sir [k + 1] != sir [i]) {
			k = pi [k] ; 
		}
		if (sir [k + 1] == sir [i]) {
			k += 1 ; 
		}
		pi [i] = k ;
		if (pi [i] == patternSize) {
			noSol += 1 ;
			if (noSol <= 1000) {
				sol.push_back (i - 2 * patternSize) ;
			}
		} 
	} 
	fout << noSol << '\n' ; 
	for (auto &x : sol) {
		fout << x << ' ' ; 
	}
	return 0;
}