Cod sursa(job #2438536)

Utilizator red_devil99Mancunian Red red_devil99 Data 12 iulie 2019 17:50:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;
#include <string>
#include <vector>


void prefix(std::vector<int> &pi, string &A){
	int n = A.size();
	int k = 0, i;
	pi.resize(n);
	
	for( i = 1, pi[0] = 0;i < n;i++){
		while(k && (A[k] != A[i])){
         k = pi[k-1];
		}

	
	if(A[k] == A[i]){
		++k;

	}
	pi[i] = k;
    }
}
std::vector<int> match(std::vector<int> &pi, string &A, string &B, int &N){
	int n = A.size();
	int m = B.size();
	int q = 0;
	std::vector<int> pozition;
	for (int i = 0; i < m; i++){
		while(q && A[q] != B[i]){
			q = pi[q-1];
		}
		if(A[q] == B[i]){
			q++;
		}
		if(q == n && ++N <= 1000){
            pozition.push_back(i-n+1);
		}
	}
	return pozition;
}

int main(){
	string A;
	string B;
	std::vector<int> pi;
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	int N = 0;
	fin >> A;
	fin >> B;
	prefix(pi, A);
    std::vector<int> poz = match(pi, A, B, N);
    fout << N << '\n';
    for (int i = 0; i < poz.size(); i++){
    	fout << poz[i] <<" ";
    }
    return 0;

}