Cod sursa(job #2838095)

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

using namespace std;

#define NM 2000002

int pi[NM],rez[1001],nr,n,m,nrr;
char T[NM],P[NM];///sirul si modelul (pattern-ul)
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calculPi(char P[])
 {
	int i,k;
	m=strlen(P+1);
	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()
{
    int i,k;
	nr = 0;
	n = strlen(T+1);
	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[nrr]=i-m;
            }

		}
	}
}

int main()
{
    int i;
 	fin >> P+1 >> T+1;

	calculPi(P);
 	KMP();

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