Cod sursa(job #2739199)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 7 aprilie 2021 07:35:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 2e6+5;

int phi[2 * NMAX];
vector<int>sol;

void kmp(string &s)
{
    phi[0] = -1;
    for(int i = 1 ; i < s.size() ; i++)
    {
        int k = i-1;
        while(phi[k] != -1 && s[phi[k]+1] != s[i])
            k = phi[k];
        if(s[i] == s[phi[k]+1])
            phi[i] = phi[k]+1;
        else
            phi[i] = -1;
    }
}

string a, b;
string s;

int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);
	getline(fin, a);
	getline(fin, b);
	s = a + "$" + b;
	kmp(s);
	int na = a.size();
	int nb = b.size();
	for (int i = na + 1; i < s.size(); i++)
	{
		if (phi[i] == na - 1)
			sol.push_back(i-2*na);
	}
	fout << sol.size() << '\n';
	int m = min(1000, (int)sol.size());
	for (int i = 0; i < m; i++)
		fout << sol[i] << ' ';
	fout << '\n';
	return 0;
}