2Provatempo

#include<iostream>

using namespace std;

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

int match(char *T, char *P, int dimT, int dimP);
int not_match(char *T, char x, int dimT);

//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)
        return true;
    else
        if(!dimT)
            return false;

    X->salta = not_match(T,*P,dimT);
    X->prendi = match(T+X->salta,P,dimT-X->salta,dimP);


    return F(T+X->prendi+X->salta,P+X->prendi,dimT-(X->prendi+X->salta),dimP-X->prendi,X+1);


}//F
//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)

/* -- CASO BASE --
- Se dimP == 0 --> ho trovato il match completo
- Se dimT == 0 --> Sono arrivato alla fine di T senza trovare il match

Assumendo PRE_F_ric --> la POST_ric è dimostrata
 -- CASO INDUTTIVO --
 //PRE_F_ric=(T+X->prendi ha dimT-(X->prendi+X->salta) elementi definiti e P+X->prendi ne ha dimP-X->prendi, X+1 ha gli elementi che ci servono)
 Ricorsione

 -La PRE_F_ric è vera banalmente
-La post è dimostrata dalla POST_F_ric, dato che un match di P è presente in T sse un match (P+(numero di elementi presi)) è presente in (T+(il numero di elementi saltati e presi))
//POST_ric=(restituisce true sse esiste un match completo (con eventuali buchi) di (P+(numero di elementi presi)) in (T+(il numero di elementi saltati e presi)) e, se il match c’è, (X+1) contiene le coppie che corrispondono al 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 || !dimP)
        return 0;

    if(*P == *T)
        return 1+match(T+1,P+1,dimT-1,dimP-1);
    else
        return 0;


}//match
//POST_m=(deve  restituire  la  lunghezza del massimo  prefisso  di  P  che  matcha  a  partire  da  T[0]  in posizioni contigue, cioè senza buchi)

/* -- CASO BASE --
 Se  dimP o dimT sono uguali a 0, la funzione ritorna 0, che e' la lunghezza del match piu' lungo che inizia in *T. Vale la POST_m
 Se *T!=*P la la funzione ritorna 0, che e' la lunghezza del match piu' lungo che inizia in T[0]. Vale la POST_m

   -- CAS0 RICORSIV0 --
Pre_ric=(T+1 e P+1 hanno almeno rispettivamente dimT-1 e dimP-1 elementi definiti)

chiama ricorsiva su T+1

POST_ric=(restituisce  la lunghezza del massimo prefisso  di P+1 che matcha a partire da T+1 in posizioni contigue)
Allora al termine della ricorsione, match restituisce lunghezza del match di P che inizia in T. Vale POST_m

*/

//PRE_n=(T ha dimT elementi)
int not_match(char*T, char x, int dimT){

    if(!dimT)
        return 0;

    if(*T == x)
        return 0;
    else
        return 1+not_match(T+1,x,dimT-1);


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

/*  -- CASO BASE:
- dimP==0, non ho elementi ritorno 0.
- *T==x, subito match ritono 0
CASO RICORSIVO:
PRE_ric=(T+1 ha dimT+1 elementi)
chiamata ricorsiva
POST_ric=(restituisce  il numero di elementi di T+1 da saltare per arrivare a trovare x in T+1 , partendo da T+1)

Restituisce quindi il numero di salti da T all'elemento di T che matcha x
*/
void stampa(coppia *X){

    if(X->prendi != -1 || X->salta != -1){

        cout<<"("<<X->salta<<","<<X->prendi<<")";
        return stampa(X+1);

    }
    else
        cout<<endl;



}//stampa

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;
}