Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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_match(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(dimT==0 && dimP>0)
- return false;
- else if(dimP==0)
- return true;
- X->salta=not_match(T,P[0],dimT);
- X->prendi=match(T+X->salta,P,dimT-X->salta,dimP);
- //PRE_ric=((T+(il numero di elementi saltati e presi)) ha dimT-(il numero di elementi saltati e presi) elementi definiti e (P+(numero di elementi presi)) ne ha dimP-(numero di elementi presi), (X+1) ha gli elementi che ci servono)
- return F(T+(X->salta+X->prendi),P+X->prendi, dimT-(X->salta+X->prendi), dimP-X->prendi, X+1);
- //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)
- }
- //POST_F=(restituisce true sse esiste un match completo (con eventuali buchi) di P in T e, se il match c’è, X contiene le coppie che corrispondono al match)
- /*
- DIMOSTRAZIONE induttiva
- -Casi base:
- (1)- Se dimT==0 e dimP>0 allora T è un vettore vuoto, mentre P ha degli elementi, quindi non può esserci un match
- (2)- Se dimP==0 allora P è un vettore vuoto, quindi c'è un match e X non contiene nessuna coppia dato che non c'è nessun elemento da cercare
- Quindi assumendo PRE_F nei casi base vale POST_F
- -Caso induttivo:
- -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))
- */
- //PRE_n=(T ha dimT elementi)
- int not_match(char*T, char x, int dimT)
- {
- if(dimT==0)
- return 0;
- if(T[0]==x)
- return 0;
- //PRE_n_ric=((T+1) ha dimT-1 elementi)
- return 1+not_match(T+1,x,dimT-1);
- //POST_n_ric=(restituisce 1 + il numero di elementi di (T+1) da saltare per arrivare a trovare x in (T+1), partendo da (T+1)[0])
- }
- //POST_n=(restituisce il numero di elementi di T da saltare per arrivare a trovare x in T, partendo da T[0])
- /*
- DIMOSTRAZIONE induttiva
- -Casi base:
- (1)- Se dimT==0 allora T è vuoto, quindi non ci sono elementi da saltare per trovare x
- (2)- Se T[0]==x allora per arrivare a x da T[0] occorre saltare 0 elementi
- Quindi assumendo PRE_F nei casi base vale POST_F
- -Caso induttivo:
- -La PRE_F_ric è vera dato che ci si sposta in avanti di un elemento in T, e quindi il numero di elementi definiti in (T+1) è minore di 1 rispetto a quelli in T
- -La post è dimostrata dalla POST_F_ric, dato che per arrivare a x da T[0] se T[0]!=x bisognerà saltare l'elemento T[0] più tutti gli elementi che bisognera saltare da (T+1)[0] per arrivare a x
- */
- //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_ric=((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_ric=(restituisce la lunghezza del massimo prefisso di (P+1) che matcha a partire da (T+1)[0] in posizioni contigue)
- }
- //POST_m=(deve restituire la lunghezza del massimo prefisso di P che matcha a partire da T[0] in posizioni contigue, cioè senza buchi)
- /*
- DIMOSTRAZIONE induttiva
- -Casi base:
- (1)- Se dimT==0 o dimP==0 allora T o P(o entrambi) sono vuoti, quindi non ci sono prefissi di P che matchano a partire da T[0]
- (2)- Se T[0]!=P[0] allora il prefisso di P che matcha a partire da T[0] ha lunghezza 0
- Quindi assumendo PRE_F nei casi base vale POST_F
- -Caso induttivo:
- -La PRE_F_ric è vera dato che ci si sposta in avanti di un elemento in T, e quindi il numero di elementi definiti in (T+1) è minore di 1 rispetto a quelli in T, stessa cosa per P
- -La post è dimostrata dalla POST_F_ric, dato che se T[0]==P[0] allora la lunghezza del prefisso di P che matcha a partire da T[0] è uguale a 1 + la lunghezza del prefisso di (P+1) che matcha a partire da (T+1)[0]
- */
- void stampa(coppia* X)
- {
- if(X->salta == -1 && X->prendi == -1)
- return;
- cout << '('<<X->salta<<','<<X->prendi<<") ";
- stampa(X+1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement