Cod sursa(job #1345462)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 17 februarie 2015 17:18:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef int ull;

inline  ull minim(ull a, ull b) {
	return (a < b) ? a : b;
}

#define NMAX 2000005

void make_prefix(string A, vector<ull> & pi) {
	int i, q = 0;
	int n = A.length();
	pi[0] = pi[1] = 0;
	for (i = 2; i <= n; ++i) {
		int j = pi[i - 1];
		for (;;) {
			if (A[j] == A[i - 1]) {
				pi[i] = j + 1;
				break;
			}
			if (j == 0) {
				pi[j] = 0;
				break;
			}
			j = pi[j];
		}
	}
}

int main(void) {
	int i, q = 0, n = 0;
	ifstream iff("strmatch.in");
	ofstream off("strmatch.out");
	string A,B;
	iff >> A >> B;
	vector<ull> pos;
	vector<ull> pi(A.length() + 1, 0);
	make_prefix(A, pi);
	for (i = 0; i < B.length(); ++i) {
		while (q && A[q] != B[i])
			q = pi[q];
		if (A[q] == B[i])
			++q;
		if (q == A.length()) {
			q = pi[A.length()];
			++n;
			
			pos.push_back(i - A.length() + 1);
				
			
		}
	}
	off << pos.size();
	if (pos.size()) {
		off << endl;
	}
	for (int i = 0; i <1000; ++i) {
		off << pos[i] << " ";
	}
	off.close();
}