fork(38) download
copy 
  1. // A suffix array based program to searh a given pattern in a given text
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // Structure to store information of a suffix
  8. struct suffix
  9. {
  10.     int index;
  11.     char *suff;
  12. };
  13.  
  14. // A comparison function used by sort() to compare two suffixes
  15. int cmp(struct suffix a, struct suffix b)
  16. {
  17.     return strcmp(a.suff, b.suff) < 0? 1 : 0;
  18. }
  19.  
  20.  
  21. // This is the main function that takes a string 'txt' of size n as an
  22. // argument, builds and return the suffix array for the given string
  23. int *buildSuffixArray(char *txt, int n)
  24. {
  25.     // A structure to store suffixes and their indexes
  26.     struct suffix suffixes[n];
  27.  
  28.     // Store suffixes and their indexes in an array of structures.
  29.     // The structure is needed to sort the suffixes alphabatically
  30.     // and maintain their old indexes while sorting
  31.     for (int i = 0; i < n; i++)
  32.     {
  33.         suffixes[i].index = i;
  34.         suffixes[i].suff = (txt+i);
  35.     }
  36.  
  37.     // Sort the suffixes using the comparison function
  38.     // defined above.
  39.     sort(suffixes, suffixes+n, cmp);
  40.  
  41.     // Store indexes of all sorted suffixes in the suffix array
  42.     int *suffixArr = new int[n];
  43.     for (int i = 0; i < n; i++)
  44.         suffixArr[i] = suffixes[i].index;
  45.  
  46.     // Return the suffix array
  47.     return  suffixArr;
  48. }
  49.  
  50. // A utility function to print an array of given size
  51. void printArr(int arr[], int n)
  52. {
  53.     for(int i = 0; i < n; i++)
  54.         cout << arr[i] << " ";
  55.     cout << endl;
  56. }
  57.  
  58. // Copy the code function given above
  59.  
  60. // A suffix array based search function to search a given pattern
  61. // 'pat' in given text 'txt' using suffix array suffArr[]
  62. void search(char *pat, char *txt, int *suffArr, int n)
  63. {
  64.     int m = strlen(pat); // get length of pattern, needed for strncmp()
  65.  
  66.     // Do simple binary search for the pat in txt using the
  67.     // built suffix array
  68.     int l = 0, r = n-1;  // Initilize left and right indexes
  69.     while (l <= r)
  70.     {
  71.         // Compare pat with the middle suffix in suffix array
  72.         int mid = l + (r - l)/2;
  73.         int res = strncmp(pat, txt+suffArr[mid], m);
  74.  
  75.         // If match found at the middle, print it and return
  76.         if (res == 0)
  77.         {
  78.             cout << "Pattern found at index " << suffArr[mid];
  79.             return;
  80.         }
  81.  
  82.         // Move to left half if pattern is alphabtically less than
  83.         // the mid suffix
  84.         if (res < 0) r = mid - 1;
  85.  
  86.         // Otherwise move to right half
  87.         else l = mid + 1;
  88.     }
  89.  
  90.     // We reach here if return statement in loop is not executed
  91.     cout << "Pattern not found";
  92. }
  93.  
  94. // Driver program to test above function
  95. int main()
  96. {
  97.     char txt[] = "banana";  // text
  98.     char pat[] = "nan";   // pattern to be searched in text
  99.  
  100.     // Build suffix array
  101.     int n = strlen(txt);
  102.     int *suffArr = buildSuffixArray(txt, n);
  103.  
  104.     // search pat in txt using the built suffix array
  105.     search(pat, txt, suffArr, n);
  106.  
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pattern found at index 2
https://ideone.com/1Io9eN
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!