Morris-Pratt algorithm border

「プログラミング」及び「開発」関連用語集

カテゴリー: プログラミング  閲覧数:332 配信日:2018-05-08 13:35


JavaScript


var S = 'aabaabaaa';
var A = [];
A[0] = -1;
var j = -1;
for (var i = 0; i < S.length; i++) {
 while (j >= 0 && S[i] != S[j]) j = A[j];
 j++;
 A[i+1] = j;
}
console.log(A); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]


ECMASCript2015


const S = 'aabaabaaa';
const A = [];
A[0] = -1;
let j = -1;
for (let i = 0; i < S.length; i++) {
 while (j >= 0 && S[i] != S[j]) j = A[j];
 j++;
 A[i+1] = j;
}
console.log(A); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]


C++


最初に0を格納
・10個指定
#include <iostream>
using namespace std;
#include <vector>
#include <string>

int main() {
   //vector<int> A = {1, 2, 3, 4, 5};
    vector<int> A = {0,0,0,0,0,0,0,0,0,0};

   //'aabaabaaa'
   std::vector<string> S = {"a","a","b","a","a","b","a","a","a"};

   // ここから
   A[0] = -1;
   int j = -1;
   for (int i = 0; i < S.size(); i++) {
         while (j >= 0 && S[i] != S[j]) j = A[j];
         j++;
         A[i+1] = j;
   }
   // ここまで
   
   for (int i = 0; i < (int)A.size(); i++) {
       std::cout << A[i] << std::endl;
   }

   return 0;
}

//-1
//0
//1
//0
//1
//2
//3
//4
//5
//2


・まとめて指定
#include <iostream>
using namespace std;
#include <vector>
#include <string>

int main() {
   //vector<int> A = {1, 2, 3, 4, 5};
   int A[10]={0};;

   //'aabaabaaa'
   std::vector<string> S = {"a","a","b","a","a","b","a","a","a"};

   // ここから
   A[0] = -1;
   int j = -1;
   for (int i = 0; i < S.size(); i++) {
         while (j >= 0 && S[i] != S[j]) j = A[j];
         j++;
         A[i+1] = j;
   }
   // ここまで
   
   for (int i = 0; i < (int)sizeof(A)/sizeof(*A); i++) {
       std::cout << A[i] << std::endl;
   }

   return 0;
}

//-1
//0
//1
//0
//1
//2
//3
//4
//5
//2


0を格納する必要はない

#include <iostream>
using namespace std;
#include <vector>
#include <string>

int main() {
   //vector<int> A = {1, 2, 3, 4, 5};
   int A[10];

   //'aabaabaaa'
   std::vector<string> S = {"a","a","b","a","a","b","a","a","a"};

   // ここから
   A[0] = -1;
   int j = -1;
   for (int i = 0; i < S.size(); i++) {
         while (j >= 0 && S[i] != S[j]) j = A[j];
         j++;
         A[i+1] = j;
   }
   // ここまで
   
   for (int i = 0; i < (int)sizeof(A)/sizeof(*A); i++) {
       std::cout << A[i] << std::endl;
   }

   return 0;
}

//-1
//0
//1
//0
//1
//2
//3
//4
//5
//2


動的配列
#include <iostream>
using namespace std;
#include <vector>
#include <string>

int main() {
   //vector<int> A = {1, 2, 3, 4, 5};
   vector<int> A(10);

   //'aabaabaaa'
   std::vector<string> S = {"a","a","b","a","a","b","a","a","a"};

   // ここから
   A[0] = -1;
   int j = -1;
   for (int i = 0; i < S.size(); i++) {
         while (j >= 0 && S[i] != S[j]) j = A[j];
         j++;
         A[i+1] = j;
   }
   // ここまで
   
   for (int i = 0; i < (int)A.size(); i++) {
       std::cout << A[i] << std::endl;
   }

   return 0;
}

//-1
//0
//1
//0
//1
//2
//3
//4
//5
//2


C++11


#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <array>

int main() {
   //vector<int> A = {1, 2, 3, 4, 5};
     // vector<int> A = {0,0 ,0 ,0 ,0,0,0,0,0,0};
    std::array<int, 10> A;

   //'aabaabaaa'
   std::vector<string> S = {"a","a","b","a","a","b","a","a","a"};

   // ここから
   A[0] = -1;
   int j = -1;
   for (int i = 0; i < S.size(); i++) {
         while (j >= 0 && S[i] != S[j]) j = A[j];
         j++;
         A[i+1] = j;
   }
   // ここまで
   
   for (int i = 0; i < (int)A.size(); i++) {
       std::cout << A[i] << std::endl;
   }

   return 0;
}

//-1
//0
//1
//0
//1
//2
//3
//4
//5
//2