Advertisement
Josif_tepe

Untitled

Nov 6th, 2024
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. string text;
  5.  
  6. int * LPS(const string & subStr) {
  7.     int n = subStr.size();
  8.     int * lps = new int[n];
  9.    
  10.     int j = 0;
  11.     lps[0] = 0;
  12.    
  13.     int i = 1;
  14.     while(i < n) {
  15.         if(subStr[i] == subStr[j]) {
  16.             j++;
  17.             lps[i] = j;
  18.             i++;
  19.         }
  20.         else {
  21.             if(j == 0) {
  22.                 lps[i] = 0;
  23.                 i++;
  24.             }
  25.             else {
  26.                 j = lps[j - 1];
  27.             }
  28.         }
  29.     }
  30.    
  31.     return lps;
  32. }
  33. int * reverseLPS(const string & subStr) {
  34.     int n = subStr.size();
  35.     int * lps = new int[n];
  36.    
  37.     int j = 0;
  38. //    lps[0] = 0;
  39. //    
  40.     for(int i = n - 2; i >= 0; i--) {
  41.         while(j > 0 and subStr[i] != subStr[n - j - 1]) {
  42.             j = lps[n - j];
  43.         }
  44.         if(subStr[i] == subStr[n - j - 1]) {
  45.             j++;
  46.         }
  47.         lps[i] = j;
  48.     }
  49.     for(int i = 0; i < n; i++) {
  50.         cout << lps[i] << " ";
  51.     }
  52.     return lps;
  53. }
  54. int* findAllSubStr(const string & subStr) {
  55.     int * lps = LPS(subStr);
  56.     int n = subStr.size();
  57.     int * res = new int[n];
  58.     int r = 0;
  59.    
  60.     int i = 0, j = 0;
  61.     while(i < (int) text.size()) {
  62.         if(text[i] == subStr[j]) {
  63.             i++;
  64.             j++;
  65.            
  66.             if(j == n) {
  67.                 res[r++] = i - j;
  68.                 cout << i - j << endl;
  69.                 j = lps[j - 1];
  70.             }
  71.         }
  72.         else {
  73.             if(j != 0) {
  74.                 j = lps[j - 1];
  75.             }
  76.             else {
  77.                 i++;
  78.             }
  79.         }
  80.     }
  81.    
  82.     int *res_array = new int[r];
  83.     for(int i = 0; i < r; i++) {
  84.         res_array[i] = res[i];
  85.     }
  86.    
  87.     return res_array;
  88. }
  89. int findFirstSubStr(const string & subStr) {
  90.     int * lps = LPS(subStr);
  91.     int n = subStr.size();
  92.    
  93.     int i = 0, j = 0;
  94.     while(i < (int) text.size()) {
  95.         if(text[i] == subStr[j]) {
  96.             i++;
  97.             j++;
  98.            
  99.             if(j == n) {
  100.                 return i - j;
  101.             }
  102.         }
  103.         else {
  104.             if(j != 0) {
  105.                 j = lps[j - 1];
  106.             }
  107.             else {
  108.                 i++;
  109.             }
  110.         }
  111.     }
  112.     return -1;
  113. }
  114. int findLastSubStr(const string & subStr) {
  115.     int * lps = reverseLPS(subStr);
  116.     int n = subStr.size();
  117.    
  118.     int i = text.size() - 1, j = n - 1;
  119.     while(i >= 0) {
  120.         if(text[i] == subStr[j]) {
  121.             i--;
  122.             j--;
  123.            
  124.             if(j == 0) {
  125.                 return i;
  126.             }
  127.         }
  128.         else {
  129.             if(j != n - 1) {
  130.                 j = lps[n - j - 1];
  131.             }
  132.             else {
  133.                 i--;
  134.             }
  135.         }
  136.     }
  137.     return -1;
  138. }
  139. int main() {
  140.     text = "ABABABCABABC";
  141.     string pat = "abcabcy";
  142.     int p = findLastSubStr(pat);
  143.     return 0;
  144. }
  145.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement