Cod sursa(job #2738433)

Utilizator FrostfireMagirescu Tudor Frostfire Data 5 aprilie 2021 20:28:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000000

using namespace std;

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

string s1, s2;
int phi[2*NMAX+10], ans;
vector <int> poz;

int main()
{
	fin >> s1 >> s2;
	string s = s1 + '&' + s2;
	int n1 = s1.size(), n = s.size(), i = 1, j = 0;
	while(i < n)
		{	if(s[i] == s[j])
				{	phi[i] = j + 1;
					i++;
					j++;
				}
			else
				{	if(!j)
						i++;
					else
						j = phi[j-1];
				}
		}
	for(int i=0; i<n; i++)
		if(phi[i] == n1)
			{	ans++;
				if(ans <= 1000)
					poz.push_back(i - 2 * n1);
			}
	fout << ans << '\n';
	for(auto u : poz)
		fout << u << ' ';
	cout << '\n';
	return 0;
}