Pagini recente » Cod sursa (job #761516) | Cod sursa (job #2522311) | Cod sursa (job #1375511) | Cod sursa (job #1795195) | Cod sursa (job #760272)
Cod sursa(job #760272)
#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;
}