Cod sursa(job #2129160)

Utilizator PostMaloneLiurca Daniel PostMalone Data 12 februarie 2018 16:24:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

#define minim(a, b) ((a < b) ? a : b)
#define MAX 2000005

string A, B;
int pi[MAX], pos[1024];

void make_prefix(int m)
{
	int q = 0;
	pi[1] = 0;
 
    for (int i = 2; 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()
{
	getline(input, A);  
	getline(input, B);
	getline(input, B);
	
	int m = A.size();
	int n = B.size();
	for (int i = m; i; --i) A[i] = A[i-1]; A[0] = ' ';
    for (int i = n; i; --i) B[i] = B[i-1]; B[0] = ' ';  
	
	make_prefix(m);
	
	int q = 0, p = 0;
	
    for (int i = 1; i <= n; ++i)
    {       
        while (q && A[q+1] != B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            ++q;
        if (q == m)
        {
            q = pi[m];
            ++p;
            if (p <= 1000)
                pos[p] = i-m;
        }   
    }  	

	output << p;
	for (int i = 1; i <= minim(p, 1000); ++i)
		output << pos[i] << " ";

	return 0;
}