Advertisement
Guest User

Boyer–Moore string-search algorithm

a guest
Dec 11th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. var s = WScript.StdIn.ReadLine();
  2. var t = WScript.StdIn.ReadLine();
  3. var ans = [];
  4. count = 0;
  5. S_i = 0; // s.charAt(i+j) // should change the name
  6. //j = t.length -1; // t.charAt(j)
  7.  
  8. sign = {}; // ассоциативный массив
  9. for (i = 0; i<t.length;i++) // подсчет количества повторов
  10. {
  11.     if (CheckIfContainsInT(sign, t.charAt(i)))
  12.     {
  13.         sign[t.charAt(i)]++;
  14.     }
  15.     else
  16.         sign[t.charAt(i)] = 1;
  17. }
  18. Check(sign);
  19.  
  20. while(S_i<=s.length-t.length) // last symbol
  21. {
  22.     if (s.charAt(S_i+t.length-1) != t.charAt(t.length-1))
  23.     {
  24.         //WSH.echo(s.charAt(S_i+t.length-1) + "!=" + t.charAt(t.length-1));
  25.         //WSH.echo(CheckIfContainsInT(sign, s.charAt(S_i+t.length-1)));
  26.         //WSH.echo(FindLastPosition(t, s.charAt(S_i+t.length-1)));
  27.         if (CheckIfContainsInT(sign, s.charAt(S_i+t.length-1)))
  28.         {
  29.             S_i+=FindLastPosition(t, s.charAt(S_i+t.length-1)) +1;
  30.         }
  31.         else
  32.             S_i+=t.length;
  33.     }
  34.     else
  35.     {
  36.         var l = 1;
  37.         for (k = t.length-2; k>-1;k--) // last symb is correct, so see from t.l.-2
  38.         {
  39.             if (s.charAt(S_i + k)!=t.charAt(k))
  40.             {
  41.                 if (sign[s.charAt(S_i + k)] == undefined )
  42.                 {
  43.                     var delta = t.length - FindLastPosition(t, s.charAt(S_i + k)) - l;
  44.                     if (delta>1)
  45.                         S_i+=delta;
  46.                     else
  47.                         S_i+=1;
  48.                     break;
  49.                 }
  50.                 else
  51.                 {
  52.                     S_i+= t.length - l;
  53.                     break;
  54.                 }
  55.             }
  56.             else
  57.                 l++;
  58.         }
  59.         if (l==t.length)
  60.         {
  61.             if(ans.length<10)
  62.                 ans.push(S_i);
  63.             count++;
  64.             S_i+=t.length;
  65.         }
  66.     }
  67.    
  68. }
  69.  
  70. WSH.echo("Count = " + count);
  71. Show(ans);
  72.  
  73. function Check(sign)
  74. {
  75.     for (var i in sign)
  76.         WSH.echo("'" + i + "'" + " = " + sign[i]);
  77. }
  78.  
  79. function CheckIfContainsInT (sign, ch) // DON'T WORK!
  80. {
  81.     for (var j in sign)
  82.     {
  83.         if (j == ch)
  84.             return true;
  85.     }
  86.     return false;
  87. }
  88.  
  89. function FindLastPosition(str, ch)
  90. {
  91.     for(j = str.length-1; j>-1;j--)
  92.     {
  93.         if (str.charAt(j) == ch)
  94.             return j;
  95.     }
  96. }
  97.  
  98. function Show(array)
  99. {
  100.     for (i = 0; i<array.length;i++)
  101.     {
  102.         WSH.echo(i + ": " + array[i]);
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement