Cod sursa(job #2194286)

Utilizator AgacheGabrielAgache Gabriel AgacheGabriel Data 12 aprilie 2018 19:14:13
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb

#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

char text[20000], pat[2000];

int f[20000];
vector<int> v;

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

void read()
{
	fin.getline(pat, 2000001);
	fin.getline(text, 2000001);
}

void fai(char* pat)
{
	int j = 0;
	int len = strlen(pat);
	f[0] = 0;
	for (int i = 1; i < len; i++)
	{
		while (pat[i] != pat[j] && j > 0) j = f[j-1];
		if (pat[i] == pat[j]) j++;
		f[i] = j;
	}
}

void KMP()
{
	int j = 0;
	int n = strlen(text);
	int m = strlen(pat);
	for (int i = 0; i < n; i++)
	{
		while (text[i] != pat[j] && j > 0)
			j = f[j];
		if (text[i] == pat[j])
		{
			if (j == m - 1)
			{
				v.push_back(i - m + 1);
				j = f[j];
			}
			else
				j++;
		}

	}
}

int main()
{
	read();
	fai(pat);
	KMP();
	fout << v.size()<<'\n';
	for (int i : v)
		fout << i << ' ';
    return 0;
}