Pagini recente » Cod sursa (job #1282586) | Cod sursa (job #493186) | Cod sursa (job #1627558) | Cod sursa (job #1329624) | Cod sursa (job #1393899)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("potrivire.in");
ofstream g("potrivire.out");
int N,M,ind,Nr,Sol[10005],number;
vector <int> V[35];
int DP[35][10005],last,P[10005],Ind[10005],first=10005;
char Str[10005],B[10005],A[10005];
void Read()
{
f>>N>>M;
char ch;
for(int i=1;i<=N;i++)
f>>B[i];
for(int i=1;i<=M;i++)
f>>Str[i];
}
void Build_Prefixes()
{
int i,q;
P[1]=0;
for(q=0,i=2;i<=ind;i++)
{
while(q&&A[q+1]!=A[i])
q=P[q];
if(A[q+1]==A[i])
q++;
P[i]=q;
}
}
void KMP()
{
int i,q=0;
for(i=1;i<=N;i++)
{
while(q&&A[q+1]!=B[i])
q=P[q];
if(A[q+1]==B[i])
q++;
if(q==ind)
{
Nr++;
Sol[Nr]=i-ind+1;
}
}
}
void precalcV()
{
ind=0,number=0;
for(int i=1;i<=M;i++)
{
if(Str[i]!='*')
A[++ind]=Str[i];
else
{
if(number==0 && ind==0)
first=1;
if(ind==0)
continue;
++number;
Ind[number]=ind;
for(int i=1;i<=ind;i++)
P[i]=0;
Build_Prefixes();
KMP();
for(int i=1;i<=Nr;i++)
V[number].push_back(Sol[i]);
Nr=0;
last=ind;
ind=0;
}
}
if(ind==0)
return;
++number;
for(int i=1;i<=ind;i++)
P[i]=0;
Build_Prefixes();
KMP();
for(int i=1;i<=Nr;i++)
V[number].push_back(Sol[i]);
Nr=0;
last=ind;
Ind[number]=ind;
}
void Solve()
{
if(number==0)
{
g<<"1 1\n";
return;
}
if(V[1].size()==0)
{
g<<-1<<"\n";
return;
}
int last=V[1][0];
bool ok=1;
for(int i=2;i<=number;i++)
{
ok=0;
for(int j=0;j<V[i].size();j++)
{
if(last+Ind[i-1]-1<V[i][j])
{
last=V[i][j];
ok=1;
break;
}
}
if(ok==0)
break;
}
if(ok==0)
{
g<<-1<<"\n";
return;
}
g<<min(V[1][0],first)<<" "<<last+Ind[number]-1<<"\n";
}
int main()
{
Read();
precalcV();
Solve();
return 0;
}