カテゴリー:
プログラミング
閲覧数:333 配信日: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