Advertisement
Guest User

Untitled

a guest
Apr 26th, 2018
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.90 KB | None | 0 0
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct coppia{int salta,prendi; coppia(int a=0,int b=0){salta=a;prendi=b;}};
  6.  
  7.  
  8. bool F(char* T, char* P, int dimT, int dimP, coppia *X);
  9. int match (char* T, char*P, int dimT, int dimP);
  10. int not_match(char*T, char x, int dimT);
  11. void stampa(coppia* X);
  12.  
  13. main()
  14. {
  15.   int dimT, dimP;
  16.   char T[400],P[50];
  17.   coppia X[50];
  18.   for(int i=0; i<50; i++)
  19.     X[i]=coppia(-1,-1);
  20.   cin>> dimT>>dimP;
  21.  
  22.   for(int i=0; i<dimT; i++)
  23.     cin>>T[i];
  24.   for(int i=0; i<dimP; i++)
  25.     cin>>P[i];
  26.   cout<<"start"<<endl;
  27.   if(F(T,P,dimT,dimP,X))
  28.     stampa(X);
  29.    else
  30.     cout<<"nessun match completo"<<endl;
  31.   cout<<"end"<<endl;
  32. }
  33.  
  34. //PRE_F=(T ha dimT elementi definiti e P ne ha dimP, X ha gli elementi che ci servono)
  35. bool F(char* T, char* P, int dimT, int dimP, coppia *X)
  36. {
  37.     if(dimT==0 && dimP>0)
  38.         return false;
  39.     else if(dimP==0)
  40.         return true;
  41.     X->salta=not_match(T,P[0],dimT);
  42.     X->prendi=match(T+X->salta,P,dimT-X->salta,dimP);
  43.    
  44.     //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)
  45.     return F(T+(X->salta+X->prendi),P+X->prendi, dimT-(X->salta+X->prendi), dimP-X->prendi, X+1);
  46.     //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)
  47.  
  48. }
  49. //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)
  50. /*
  51. DIMOSTRAZIONE induttiva
  52. -Casi base:
  53.     (1)- Se dimT==0 e dimP>0 allora T è un vettore vuoto, mentre P ha degli elementi, quindi non può esserci un match
  54.     (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
  55.     Quindi assumendo PRE_F nei casi base vale POST_F
  56. -Caso induttivo:
  57.     -La PRE_F_ric è vera banalmente
  58.     -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))  
  59. */
  60.  
  61. //PRE_n=(T ha dimT elementi)
  62. int not_match(char*T, char x, int dimT)
  63. {
  64.     if(dimT==0)
  65.         return 0;
  66.     if(T[0]==x)
  67.         return 0;
  68.     //PRE_n_ric=((T+1) ha dimT-1 elementi)
  69.     return 1+not_match(T+1,x,dimT-1);
  70.     //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])
  71. }
  72. //POST_n=(restituisce il numero di elementi di T da saltare per arrivare a trovare x in T, partendo da T[0])
  73. /*
  74. DIMOSTRAZIONE induttiva
  75. -Casi base:
  76.     (1)- Se dimT==0 allora T è vuoto, quindi non ci sono elementi da saltare per trovare x
  77.     (2)- Se T[0]==x allora per arrivare a x da T[0] occorre saltare 0 elementi
  78.     Quindi assumendo PRE_F nei casi base vale POST_F
  79. -Caso induttivo:
  80.     -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
  81.     -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
  82. */
  83.  
  84. //PRE_m=( T ha dimT elementi definiti e P ne ha dimP)
  85. int match (char* T, char*P, int dimT, int dimP)
  86. {
  87.     if(dimT==0 || dimP==0)
  88.         return 0;
  89.     if(T[0]!=P[0])
  90.         return 0;
  91.     //PRE_m_ric=((T+1) ha dimT-1 elementi definiti e (P+1) ne ha dimP-1)
  92.     return 1+match(T+1,P+1,dimT-1,dimP-1);
  93.     //POST_m_ric=(restituisce la lunghezza del massimo prefisso di (P+1) che matcha a partire da (T+1)[0] in posizioni contigue)
  94. }
  95. //POST_m=(deve restituire la lunghezza del massimo prefisso di P che matcha a partire da T[0] in posizioni contigue, cioè senza buchi)
  96. /*
  97. DIMOSTRAZIONE induttiva
  98. -Casi base:
  99.     (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]
  100.     (2)- Se T[0]!=P[0] allora il prefisso di P che matcha a partire da T[0] ha lunghezza 0
  101.     Quindi assumendo PRE_F nei casi base vale POST_F
  102. -Caso induttivo:
  103.     -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
  104.     -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]
  105. */
  106.  
  107. void stampa(coppia* X)
  108. {
  109.     if(X->salta == -1 && X->prendi == -1)
  110.         return;
  111.     cout << '('<<X->salta<<','<<X->prendi<<") ";
  112.     stampa(X+1);
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement