Cod sursa(job #1170964)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 14 aprilie 2014 22:09:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>

#define e '\n'

using namespace std;

#define FILE "strmatch"

#define INF 1023456789
#define ll long long

#ifdef FILE
ifstream f(string (string(FILE) + ".in").c_str());
ofstream g(string (string(FILE) + ".out").c_str());
#endif
#ifndef FILE
#define f cin
#define g cout
#endif

string sach, needle;
vector<int> rez;
int pi[2000005];

int i, j, n, m, t;

int main() {

	f >> needle;
	f >> sach;

	int pos = 0;
	for (i=1; i<needle.size(); i++) {
		while (needle[i] != needle[pos] && pos > 0) {
			pos = pi[pos-1];
		}
		if (needle[i] == needle[pos]) {
			pos++;
		}
		pi[i] = pos;
	}

//	for(i=0; i<needle.size(); i++) {
//		g << pi[i] << " ";
//	}

	pos = 0;
	for(i=0; i<sach.size(); i++) {
		while (sach[i] != needle[pos] && pos > 0) {
			pos = pi[pos-1];
		}
		if (sach[i] == needle[pos]) {
			pos ++;
			if (pos == needle.size()) {
				rez.push_back(i - pos + 1);
				pos = pi[pos-1];
			}
		}
	}

	g << rez.size() << e;
	for (i=0; i<rez.size() && i<1000; i++) {
		g << rez[i] << " ";
	}

	return 0;

}