Cod sursa(job #2194288)

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

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

using namespace std;

char text[2000010], pat[2000010];

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

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

int mini(int a,int b)
{
    return a<b ? a:b;
}

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 = 0;i<mini(1000,v.size());i++)
        fout<<v[i]<<' ';
    return 0;
}