Morris-Pratt algorithm border

アルゴリズム探索アルゴリズム

一覧

 状態:-  閲覧数:525  投稿日:2018-05-03  更新日:2018-05-15  

内容


ABABCA
GCAGAGAG
AABAABAAA

ABABCA

 閲覧数:218 投稿日:2018-05-03 更新日:2018-05-03 

正解


篠原研究室
検索文字列パターン - A B A B C A
border -1 0 0 1 2 0 1


GCAGAGAG

 閲覧数:231 投稿日:2018-05-04 更新日:2018-05-04 

正解


篠原研究室
検索文字列パターン - G C A G A G A G
border -1 0 0 0 1 0 1 0 1
Université de Rouen
検索文字列パターン G C A G A G A G -
border -1 0 0 0 1 0 1 0 1


AABAABAAA

 閲覧数:225 投稿日:2018-05-05 更新日:2018-05-05 

篠原研究室

検索文字列パターン - A A B A A B A A A
border -1 0 1 0 1 2 3 4 5 2
JavaScript
function calc_border(pat) {
   var m = pat.length;
   var t = -1;
   var bord = new Array();
   bord.push(-1);

   for (var i = 0; i < m; i++) {
       while (t >= 0 && pat[t] != pat[i]) {
           t = bord[t];
       }
       t++;

       bord.push(t);
   }
   return bord;
}

var pat = 'aabaabaaa';
console.log(calc_border(pat)); //(10) [-1, 0, 1, 0, 1, 2, 3, 4, 5, 2]



文字列の頭良い感じの線形アルゴリズムたち

検索文字列パターン - A A B A A B A A A
border _ 0 1 0 1 2 3 4 5 2
実行できるよう補完したC++コード
#include <iostream>
using namespace std;
#include <vector>

int main() {
   std::vector<int> A;
   std::vector<int> S;

   A.push_back(1);
   S.push_back(1);

   // ここから
   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;
}


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


・最初に0を格納。まとめて指定
#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




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]



下記for文が何のプログラミング言語で書かれているか知りたい
要素数だけを指定して配列を作成したい


Knuth–Morris–Pratt algorithm border

border

コメント投稿(ログインが必要)



週間人気ページランキング / 6-26 → 7-2
順位 ページタイトル抜粋 アクセス数
1 ベクトル | 数学 | プログラミング用語 268
1 curl | HTTPクライアント(ネットワーク) | プログラミング用語 268
2 ルーター | ネットワーク | プログラミング用語 267
3 Flash Video | コンテナフォーマット | プログラミング用語 265
4 正規表現 | プログラミング | プログラミング用語 261
5 デーモン | Linux | プログラミング用語 258
6 ユースケース | 開発 | プログラミング用語 237
7 チェックアウト | バージョン管理システム(開発) | プログラミング用語 158
8 YouTube | API | プログラミング用語 128
9 Linux | プログラミング用語 45
10 PowerShell | スクリプト | プログラミング用語 44
11 可搬性 | プログラミング | プログラミング用語 33
12 クローラ | 検索エンジン | プログラミング用語 25
13 Subversion | バージョン管理システム(開発) | プログラミング用語 23
14 アンチパターン | プログラミング | プログラミング用語 11
15 プログラミング用語 9
16 deflate | ネットワーク | プログラミング用語 8
17 Nginx / Nginxとは?/ Apacheとの違い | プログラミング用語 6
17 YouTubeに掲載されている動画を、ユーザーが作成したWebサービス上で再生する方法 | プログラミング用語 6
17 WebLogic | アプリケーションサーバ(サーバ) | プログラミング用語 6
2022/7/3 1:01 更新