Cod sursa(job #1856240)

Utilizator ArkinyStoica Alex Arkiny Data 24 ianuarie 2017 18:08:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;

ifstream in("potrivire.in");
ofstream out("potrivire.out");

char s1[2000010];
char s2[2000010];

int prefix[2000010],nr=0;
vector<int> rez;

void make_prefix(char s[])
{
	int l = strlen(s);

	int i = 0, j = 1;

	for (; j < l; ++j)
	{
		while (i > 0 && s[i] != s[j])
			i = prefix[i - 1];

		if (s[i] == s[j])
			++i;

		prefix[j] = i;
	}

}

void KMP(char s1[], char sub[])
{
	int l1 = strlen(s1);
	int l2 = strlen(sub);

	make_prefix(sub);

	int i = 0, j = 0;

	for (; j < l1;++j)
	{
		while (i > 0 && s1[j] != sub[i])
			i = prefix[i - 1];

		if (s1[j] == sub[i])
			++i;

		if (i == l2)
		{
			++nr;
			if (nr <= 1000)
				rez.push_back(j - i + 1);
		}

	}

}

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

	KMP(s1, s2);

	out << nr << "\n";

	for (int i = 0; i < rez.size(); ++i)
		out << rez[i] << " ";
	

	return 0;
}