Cod sursa(job #2373745)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 7 martie 2019 15:06:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 2e6 + 7;

int prefix[DIM];

string a;
string b;

vector <int> pos;

int main()
{
	string a;
	string b;
	
	in >> a >> b;
	
	int n = b.size();
	int m = a.size();
	
	a = ' ' + a;
	b = ' ' + b; 
	
	int k = 0;
	
	for(int i = 2; i <= m; i++)
	{
		while(k != 0 && a[k + 1] != a[i])
			k = prefix[k];
		
		if(a[k + 1] == a[i])
			k++;
		
		prefix[i] = k;
	}
	
	k = 0;
	int nr = 0;
	
	for(int i = 1; i <= n; i++)
	{
		while(k != 0 && a[k + 1] != b[i])
			k = prefix[k];
		
		if(a[k + 1] == b[i])
			k++;
		
		if(k == m)
		{
			k = prefix[m];
			nr++;
			
			if(pos.size() < 1000)
			{
				pos.push_back(i - m);
			}
		}
	}
	
	out << nr << '\n';
	
	for(auto i : pos)
		out << i << ' ';
}