Cod sursa(job #1541446)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 4 decembrie 2015 01:51:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <string>
#include <assert.h>

#define MaxN 2000005

using namespace std;

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

string s1, s2;
int pi[MaxN];

void build_pi() {
	int q = -1;

	pi[0] = -1;
	for (size_t i = 1; i < s1.length(); ++i) {
		while (q > -1 && s1[i] != s1[q + 1])
			q = pi[q];
		if (s1[i] == s1[q + 1])
			++q;
		pi[i] = q;
	}
}

int main()
{
	fin >> s1 >> s2;

	build_pi();

	int res[10001];
	int N = 0;
	int q = -1;
	for (size_t i = 0; i < s2.length(); ++i) {
		while (q > -1 && s2[i] != s1[q + 1]) {
			q = pi[q];
		}

		if (s1[q + 1] == s2[i])
			++q;

		if (q == s1.length() - 1) {
			q = pi[q];
			++N;
			if (N <= 10000) {
				res[N] = i - s1.length();
			}
		}
	}

	fout << N << '\n';
	for (int i = 1; i <= N; ++i)
		fout << res[i] + 1 << ' ';

	return 0;
}