Cod sursa(job #1161511)

Utilizator Kira96Denis Mita Kira96 Data 31 martie 2014 11:52:09
Problema Marbles Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#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;
}