Pagini recente » Cod sursa (job #856190) | Cod sursa (job #1207822) | Cod sursa (job #2073701) | Cod sursa (job #1934216) | Cod sursa (job #1161511)
#include <fstream>
#include <cstring>
#include <cstdlib>
#define DIM 10010
using namespace std;
ifstream f("potrivire.in");
ofstream g("potrivire.out");
int n, m, i, j, p[DIM], v[DIM], nr, q;
char a[DIM], b[DIM];
void prefix(){
p[1]=0;
for(i=2; i<=m; i++)
{
q=p[i-1];
while( (b[i]!=b[q+1] && b[i]!='*' && b[q+1]!='*') && q!=0)
q=p[q];
if(b[i]==b[q+1] || b[i]=='*' || b[q+1]=='*')
p[i]=q+1;
else
p[i]=0;
}
}
void kmp(){
q=0;
for(i=1; i<=n; i++)
{
while( (a[i]!=b[q+1] && a[i]!='*' && b[q+1]!='*') && q!=0)
q=p[q];
if(a[i]==b[q+1] || a[i]=='*' || b[q+1]=='*')
q++;
if(q==m)
{
g<<i-m<<' '<<i<<"\n";
exit(0);
}
}
}
int main(){
f>>n>>m;
f.get();
f.get(a+1, DIM);
f.get();
f.get(b+1, DIM);
prefix();
kmp();
return 0;
}