Cod sursa(job #760272)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 20 iunie 2012 19:26:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
int v[10001];
char a[10001],b[10001],c[10001];
void prefix(char c[], int n)
{
	int q,i;
	q=0;
	v[0]=0;
	v[1]=0;
	for(i=2;i<=n;i++) {
		while((q)&&(c[i]!=c[q+1]))
			q=v[q];
		if(c[i]==c[q+1])
			q++;
		v[i]=q;
	}
}
int main ()
{
	int n,m,i,j,st,dr,l,q,poz,d;
	ifstream f("potrivire.in");
	ofstream g("potrivire.out");
	f>>n>>m>>(a+1)>>(b+1);
	f.close();
	while((b[m]=='*')&&(m>0))
		m--;
	st=-1;
	dr=-1;
	if(b[1]=='*')
		st=0;
	i=1;
	if(m==0) {
		st=0;
		dr=-1;
	}
	while(i<=m) {
		while(b[i]=='*')
			i++;
		l=0;
		while((b[i]!='*')&&(i<=m)) {
			l++;
			c[l]=b[i];
			i++;
		}
		prefix(c,l);
		q=0;
		d=0;
		for(j=1;j<=n;j++) {
			while((q)&&(a[j]!=c[q+1]))
				q=v[q];
			if(a[j]==c[q+1])
				q++;
			if(q==l) {
				q=v[l];
				poz=j-l;
				if(poz>dr) {
					d=1;
					break;
				}
			}
		}
		if(d==1) {
			dr=poz+l-1;
			if(st==-1)
				st=poz;
		}
		else {
			dr=-1;
			break;
		}
	}
	if(dr!=-1) {
		g<<st+1<<" "<<dr+1;
	}
	else g<<"-1";
	g.close();
	return 0;
}