Cod sursa(job #2765273)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 26 iulie 2021 03:52:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector<int> results;
int count = 0;

void kmp(string text,string pattern)
{
	int size = pattern.size();
	int table[size];
	table[0] = 0;
	int k = 0;
	for(int i = 1; i < size; i++) {
		while (k > 0 && pattern[k] != pattern[i] )
		{
			k = table[k-1];
		}
		if (pattern[k] == pattern[i])
		{
			k = k + 1;
		}
		table[i] = k;
	}
	// for (int i = 0; i < size; i++)
	// 	cout << table[i] << " ";
	// cout << "\n";
	
	int matched_pos=0;
	for(int current=0; current< text.length(); current++) {
		while (matched_pos > 0 && pattern[matched_pos] != text[current] )
			matched_pos = table[matched_pos-1];
			
		if(pattern[matched_pos] == text[current])
			matched_pos = matched_pos + 1;
			
		if( matched_pos == (pattern.length())) {
			if (results.size() < 1000)
				results.push_back(current - (pattern.length() - 1));
			count++;
			matched_pos = table[matched_pos-1];
		}
	}
}
int main()
{
	string text, pattern;
	f >> pattern;
	f >> text;
	
	kmp(text,pattern);
	g << count << "\n";
	for (int i = 0; i < results.size(); i++)
		g << results[i] << " ";
	return 0;
}