Cod sursa(job #2580962)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 14 martie 2020 13:31:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[N],poz[1024],m,n,cnt;
char a[N],b[N];

void make_prefix()
{
	int i, q = 0;

	for (i = 2, pi[1] = 0; i <= m; ++i)
	{
		while (q && a[q+1] != a[i])
        {
			q = pi[q];
        }
		if (a[q+1] == a[i])
        {
			++q;
        }
		pi[i] = q;
	}
}
int main()
{
    char car;
    fin>>noskipws>>car;
    while(car!='\n')
    {
        a[++n]=car;
        fin>>noskipws>>car;
    }
    fin>>noskipws>>car;
    while(car!='\n')
    {
        b[++m]=car;
        fin>>noskipws>>car;
    }

    make_prefix();

    int q=0;

    for (int i = 1; i <= m; ++i)
	{
		while (q && a[q+1] != b[i])
        {
			q = pi[q];
        }
		if (a[q+1] == b[i]) q++;

		if (q == n)
		{
			q = pi[n];
			cnt++;
			if (cnt <= 1000) poz[cnt] = i-n;
		}
	}
	fout<<cnt<<'\n';
    for(int i=1;i<=min(cnt,1000);i++)
        fout<<poz[i]<<" ";
}