Cod sursa(job #2838122)

Utilizator ionicaion ionica Data 23 ianuarie 2022 10:14:24
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

#define NM 2000010

int pi[NM],nr,n,m,nrr;
string T,P;///sirul si modelul (pattern-ul)
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calculPi()
 {
	int i,k;
	pi[1] = 0;
	k = 0;

	for (i = 2; i <= m; i++)
    {
		while (k > 0 && P[i]!=P[k + 1])
			k = pi[k];

		if (P[i]==P[k + 1])
			k++;

		pi[i] = k;
	}
}

int KMP()
{
    vector<int>rez;
    int i,k;
	nr = 0;
	nrr=0;
	k = 0;

	for (i = 1; i <=n ; i++)
    {
		while (k > 0 && T[i]!=P[k + 1])
			k = pi[k];

		if (T[i]==P[k + 1])
			k++;

		if (k == m)
        {
			nr++;
			if(nr<=1000)
            {
                nrr++;
                rez.push_back(i-m);
            }

		}
	}
	fout<<nr<<'\n';
	for (i=0;i<nrr;i++)
		fout <<rez[i] << ' ';
}

int main()
{
 	fin >> P >> T;
 	m=P.size();
 	n=T.size();
 	P=" "+P;
 	T=" "+T;

	calculPi();
 	KMP();
	return 0;
}