Cod sursa(job #2450528)

Utilizator r00t_Roman Remus r00t_ Data 23 august 2019 16:44:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <queue>
#include <tuple>
#include <limits>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;

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

#define ff first
#define ss second

int lps[2000100];

void calcLPS(string pat)
{
	int j = 0, i = 1;
	lps[0] = 0;
	while(i < pat.size())
	{
		if (pat[i] == pat[j])
		{
			lps[i] = j + 1;
			j++;
			i++;
		}
		else
		{
			while (pat[i] != pat[j] && j > 0) 
				j = lps[j - 1];
			if (pat[i] == pat[j])
				lps[i] = j + 1;
			else
				i++;
		}


	}
}

void kmpSearch(string &needle, string &haystack)
{
	vector<int>sol;
	int i = 0, j = 0;
	while (i < haystack.size())
	{
		if (needle[j] == haystack[i]) i++, j++;
		else
		{
			while (j > 0 && needle[j] != haystack[i])
				j = lps[j - 1];
			
			if (j == 0 && needle[j] != haystack[i]) i++;
		}

		if (j == needle.size()) {
			sol.push_back(i - needle.size());
		} 

	}
	fout << sol.size() << '\n';
	for (i = 0; i < sol.size(); i++)
	{
		fout << sol[i] << ' ';
	}
}



int main()
{
	string needle, haystack;
	fin >> needle >> haystack;
	calcLPS(needle);
	kmpSearch(needle, haystack);

}