カテゴリー:
アルゴリズム
閲覧数:344 配信日:2018-05-05 08:04
篠原研究室
| 検索文字列パターン | - | A | A | B | A | A | B | A | A | A |
|---|---|---|---|---|---|---|---|---|---|---|
| border | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 2 |
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 |
#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文が何のプログラミング言語で書かれているか知りたい
・要素数だけを指定して配列を作成したい