Cod sursa(job #2380970)

Utilizator VadimCCurca Vadim VadimC Data 15 martie 2019 19:01:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

#define NMax 2000010

string A, B;
int n, m;
int urm[NMax];

vector<int> poz;

void prefix(string &);
void solve();

int main(){
	fin >> A >> B;
	m = A.size();
	n = B.size();
	prefix(A);
	solve();
	
	fout << poz.size() << '\n';
	for(int i = 0; i < poz.size() && i < 1000; i++) fout << poz[i] << ' ';
}

void prefix(string & A){
	int x, k;
	urm[0] = -1;
	k = -1;
	for(x = 1; x < m; x++){
		while(k >= 0 && A[k + 1] != A[x]) k = urm[k];
		if(A[k + 1] == A[x]) k++;
		urm[x] = k;
	}
}

void solve(){
	int i, x;
	x = -1;
	for(i = 0; i < n; i++){
		while(x >= 0 && A[x + 1] != B[i]) x = urm[x];
		if(A[x + 1] == B[i]) x++;
		if(x == m - 1){
			poz.push_back(i - m + 1);
			x = urm[x];
		}
	}
}