fork(4) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. void computeLPSArray(char *pat, int M, int *lps)
  4. {
  5.     int len = 0;  // lenght of the previous longest prefix suffix
  6.     int i;
  7.  
  8.     lps[0] = 0; // lps[0] is always 0
  9.     i = 1;
  10.  
  11.     // the loop calculates lps[i] for i = 1 to M-1
  12.     while(i < M)
  13.     {
  14.        if(pat[i] == pat[len])
  15.        {
  16.          len++;
  17.          lps[i] = len;
  18.          i++;
  19.        }
  20.        else // (pat[i] != pat[len])
  21.        {
  22.          if( len != 0 )
  23.          {
  24.            // This is tricky. Consider the example AAACAAAA and i = 7.
  25.            len = lps[len-1];
  26.  
  27.            // Also, note that we do not increment i here
  28.          }
  29.          else // if (len == 0)
  30.          {
  31.            lps[i] = 0;
  32.            i++;
  33.          }
  34.        }
  35.     }
  36. }
  37. void computeLPSArray2(char *pat, int M, int *lps)
  38. {
  39.     int len = 0;  // lenght of the previous longest prefix suffix
  40.     int i;
  41.  
  42.     lps[0] = 0; // lps[0] is always 0
  43.     i = 1;
  44.  
  45.     // the loop calculates lps[i] for i = 1 to M-1
  46.     while(i < M)
  47.     {
  48.        if(pat[i] == pat[len])
  49.        {
  50.          len++;
  51.          lps[i] = len;
  52.          i++;
  53.        }
  54.        else // (pat[i] != pat[len])
  55.        {
  56.          if( len != 0 )
  57.          {
  58.            // This is tricky. Consider the example AAACAAAA and i = 7.
  59.            len = len-1;
  60.  
  61.            // Also, note that we do not increment i here
  62.          }
  63.          else // if (len == 0)
  64.          {
  65.            lps[i] = 0;
  66.            i++;
  67.          }
  68.        }
  69.     }
  70. }
  71. int main() {
  72. 	char pat[]="aabcbabc";
  73. 	int *lps=new int[7];
  74. 	computeLPSArray(pat,7,lps);
  75. 	for(int i=0;i<7;++i)
  76. 		cout<<pat[i]<<"  ";
  77. 	cout<<endl;
  78. 	for(int i=0;i<7;++i)
  79. 		cout<<lps[i]<<"  ";
  80. 	computeLPSArray2(pat,7,lps);
  81. 	cout<<endl;
  82. 	for(int i=0;i<7;++i)
  83. 		cout<<lps[i]<<"  ";
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a  a  b  c  b  a  b  
0  1  0  0  0  1  0  
0  1  0  0  0  1  0
https://ideone.com/qiSrUo
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!