Cod sursa(job #1875695)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 11 februarie 2017 14:18:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <string.h>
#define VAL 4000005

using namespace std;

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

char P[VAL];
char T[VAL];
char TT[VAL];
int FF[VAL];
int n,i,r, L, x;
vector<int> v;

int main()
{
	fin>>P;
	fin>>T;
	L=strlen(T);
	TT[0]='\0';
	strcat(TT,P);
	strcat(TT,"*");
	strcat(TT,T);
	FF[0]=0;
	n=strlen(TT);
	for (i=1;i<n;i++)
	{
		r=FF[i-1];
		while (r>0)
		{
			if (TT[r]==TT[i])
				break;
			else
				r=FF[r-1];
		}
		if (TT[r]==TT[i])
			FF[i]=1+r;
		else
			FF[i]=0;
	}
	r=strlen(P);
	x=L+1;
	for (i=n-1;i>n-1-L;i--)
	{
        x--;
        if (FF[i]==r)
          v.push_back(x-r);
    }
    fout << v.size() << '\n';
    for (i=v.size()-1; i>=0; i--)
      fout << v[i] << " ";
	fin.close();
	fout.close();
	return 0;
}