2compitino

#include<iostream>

using namespace std;

struct coppia{int salta,prendi; coppia(int a=0,int b=0){salta=a;prendi=b;}};

bool F(char* T, char* P, int dimT, int dimP, coppia *X);
int match (char* T, char*P, int dimT, int dimP);
int not_matc(char*T, char x, int dimT);
void stampa(coppia *X);

main()
{
  int dimT, dimP;
  char T[400],P[50];
  coppia X[50];
  for(int i=0; i<50; i++)
    X[i]=coppia(-1,-1);
  cin>> dimT>>dimP;

  for(int i=0; i<dimT; i++)
    cin>>T[i];
  for(int i=0; i<dimP; i++)
    cin>>P[i];
  cout<<"start"<<endl;
  if(F(T,P,dimT,dimP,X))
    stampa(X);
   else
    cout<<"nessun match completo"<<endl;
  cout<<"end"<<endl;
}

  //PRE_F=(T ha dimT elementi definiti e P ne ha dimP, X ha gli elementi che ci servono)
bool F(char* T, char* P, int dimT, int dimP, coppia *X){
    if(dimP<=0)
        return true;
    if(dimT<=0)
        return false;
    X[0].salta = not_matc(T,P[0],dimT);
    X[0].prendi = match(T + X[0].salta,P,dimT - X[0].salta,dimP);
    /*
    PRE_ric_F(T+X[0].salta+X[0].prendi ha dimT-X[0].salta-X[0].prendi elementi definiti
    e P+X[0].prendi ne ha dimP-X[0].prendi, X+1 ha gli elementi che ci servono
    */
    F(T+X[0].salta+X[0].prendi,P+X[0].prendi,dimT-X[0].salta-X[0].prendi,dimP-X[0].prendi,X+1);
    /*
    POST_ric_F: restituisce true sse esiste un match completi (con eventuali buchi) di P+X[0].prendi in
    T+X[0].salta+X[0].prendi e, se il match c'e', X+1 contiene le coppie che corrispondono al match)
    */
}
/*POST_F=(restituisce true sse esiste un match completo (con eventuali buchi) d P in T e, se il match
c’è, X contiene le coppie che corrispondono al match)
*/

/*
    CORRETTEZZA:
    assumiamo che valga la pre, allora dimostriamo la pre_ric di F.
    Se T nella PRE aveva dimT elementi definiti allora vale che T+X[0].salta+X[0].prendi ha dimT-X[0].salta-X[0].prendi
    elementi definiti. X[0].salta+X[0].prendi sara' sempre piu' piccolo di T quindi la PRE e' OK.
    Inoltre P+X[0].prendi ha dimP-X[0].prendi elementi definiti. X+1 contiene gli elementi precedenti.

    Se vale la pre_ric allora vale la post_ric, allora dimostro la post utilizzando la post_ric:
    1)Se dimP<=0 significa che il match e' stato completamente trovato. Quindi ritorno true.
    2)Se dimT<=0 significa che non e' stato trovato un match all'interno di T, quindi ritorno false.
    3)  Salvo in X->salta il numero di lettere da saltare, fino a quando non trovo una corrispondenza con P[0] in T.
        Salvo in X->prendi il numero di lettere uguali fino a quando non se ne trova una di diversa
        Richiamo quindi la funzione F, passando pero' T+le lettere gia' controllate, quindi T+X->prendi+X->salta.
        E quindi anche dimT sara' uguale a dimT-X->prendi-X->salta. Gli passo inoltre P + il numero di lettere
        di P gia' trovate in T. Quindi P+X[0].prendi. La dimensione sara' quindi dimP-X[0].prendi. Poi ovviamente X+1,
        per salvare i nuovi valori nella posizione array +1.
    1 + 2 + 3 --> POST
*/

//PRE_n=(T ha dimT elementi)
int not_matc(char*T, char x, int dimT){
    if(dimT<=0)
        return 0;
    if(T[0]==x)
        return 0;
    //PRE_n=(T+1 ha dimT-1 elementi)
    return 1 + not_matc(T+1,x,dimT-1);
    //POST_n=(restituisce il numero di elementi di T+1 da saltare per arrivare a trovare x in T+1, partendo da T[1])

}
//POST_n=(restituisce il numero di elementi di T da saltare per arrivare a trovare x in T, partendo da T[0])

/*
    CORRETTEZZA:
    assumiamo che valga la pre, allora dimostriamo la pre_ric di F.
    Se T nella PRE aveva dimT elementi allora vale che T+1 ha dimT-1 elementi definiti.

    Se vale la pre_ric allora vale la post_ric, allora dimostro la post utilizzando la post_ric:
    1) Se dimT<=0 significa che ho finito di controllare l'array T, quindi ritorno la lunghezza trovata.
    2) Se T[0]==x significa che ho trovato una corrispondenza, quindi ritorno il numero di valori diversi.
    3) Richiamo la funzione ogni volta che i valori non corrispondono, quindi una volta che si andra' ai casi base,
    verra' sommato 1 ogni volta che e' stata chiamata la funzione, quindi la lunghezza del not_match.

*/

//PRE_m=( T ha dimT elementi definiti e P ne ha dimP)
int match (char* T, char*P, int dimT, int dimP){
    if(dimT<=0||dimP<=0)
        return 0;
    if(T[0]!=P[0])
        return 0;
     /*
    PRE_m=( T+1 ha dimT-1 elementi definiti e P+1 ne ha dimP-1)
    */
    return 1 + match(T+1,P+1,dimT-1,dimP-1);
    /*
    POST_m=(deve restituire la lunghezza del massimo prefisso di P+1 che matcha a partire da T[1] in
    posizioni contigue, cioè senza buchi)
    */
}
/*
POST_m=(deve restituire la lunghezza del massimo prefisso di P che matcha a partire da T[0] in
posizioni contigue, cioè senza buchi)
*/

/*
    CORRETTEZZA:
    assumiamo che valga la pre, allora dimostriamo la pre_ric di F.
    Se T nella PRE aveva dimT elementi allora vale che T+1 ha dimT-1 elementi definiti.
    Se P nella PRE aveva dimP elementi allora vale che P+1 ha dimP-1 elementi definiti.

    Se vale la pre_ric allora vale la post_ric, allora dimostro la post utilizzando la post_ric:
    1) Se dimT<=0 significa che ho finito di controllare l'array T, quindi ritorno la lunghezza trovata.
    Oppure se dimP<=0 significa che P e' stato scorso completamente, quindi ritorno 0.
    2) Se T[0]!=P[0] significa che ho trovato una non corrispondenza, quindi ritorno il numero di valori uguali.
    3) Richiamo la funzione ogni volta che i valori corrispondono, quindi una volta che si andra' ai casi base,
    verra' sommato 1 ogni volta che e' stata chiamata la funzione, quindi la lunghezza del match.

*/



void stampa(coppia *X){
   if((*X).salta!=-1){
       cout << "(" << X[0].salta << ',' << X[0].prendi << ") " ;
   }else{
       cout << endl;
       return;
   }
   stampa(X+1);
}