fork(4) download
  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
stdin
Standard input is empty
stdout
a  a  b  c  b  a  b  
0  1  0  0  0  1  0  
0  1  0  0  0  1  0