Cod sursa(job #2456831)

Utilizator UnDragosDragos Ioana UnDragos Data 15 septembrie 2019 15:53:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
int N, M;
void prefix_table(vector<int> &table, string A)
{
	table[1] = 0;
	int i = 0;
	for (int j =2; j <= N; ++j)
	{
		while (i > 0 && A[i + 1] != A[j])
		{
			i = table[i];
		}
		if (A[i + 1] == A[j])
		{
			++i;
		}
		table[j] = i;
	}
}
void KMP(int*nr_sol,vector<int> &sol, vector<int> table, string A, string B)
{
	int i = 0;
	for (int j = 1; j <= M; j++)
	{
		while (i > 0 && A[i + 1] != B[j])
		{
			i = table[i];
		}
		if (A[i + 1] == B[j])
		{
			++i;
		}
		if (i == N)
		{
			(*nr_sol)++;
			if (sol.size() < 1000)
			{
				sol.push_back(j - N);
			}
		}
	}
}
int main()
{
	string A, B;
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin >> A >> B;
	A = " " + A;
	B = " " + B;
	N = A.size() - 1;
	M = B.size() - 1;
	vector<int> table(N+1);
	prefix_table(table, A);
	vector<int> sol;
	int nr_sol = 0;
	KMP(&nr_sol,sol, table, A, B);
	cout << nr_sol << "\n";
	for (auto i : sol)cout << i << " ";
	cout << "\n";
	return 0;

}