/****************************/
/* 文字列探索 */
/* coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;
public class Test {
public static void main(String args[])
{
long tm1 = System.currentTimeMillis();
int N = 1000201;
int N1 = 5000;
int N2 = 200;
char pattern1[][] = new char [N1][N2];
char text1[] = new char[N];
Random rn = new Random();
// テキストと探索データの生成
int n = 0;
for (int i1 = 0; i1 < N; i1++) {
text1[i1] = (char)((char)(65 + 58 * rn.nextDouble()));
if (n < N1 && i1 >= 2*N2 && (i1 % N2) == 0) {
int k = i1 - N2 - N2 / 2 - 1;
for (int i2 = 0; i2 < N2; i2++) {
pattern1[n][i2] = text1[k];
k++;
}
if (n % 2 > 0) // 存在しないデータの作成
pattern1[n][N2/2] = '(';
n++;
}
}
String pattern[] = new String [N1];
for (int i1 = 0; i1 < N1; i1++)
pattern[i1] = new String(pattern1[i1]);
String text = new String(text1);
long tm2 = System.currentTimeMillis();
System.out.printf("***初期設定終了： %d ms***\n", (int)(tm2-tm1));
// 検索
System.out.printf("テキスト文字数 %d 探索パターン数 %d 探索パターン文字数 %d\n", N, n, N2);
// String クラスの indexOf
System.out.printf("String クラスの indexOf\n");
tm1 = System.currentTimeMillis();
int hit = 0;
for (int i1 = 0; i1 < n; i1++) {
int sw = text.indexOf(pattern[i1]);
if (sw < 0)
hit++;
}
tm2 = System.currentTimeMillis();
System.out.printf(" 探索時間： %d ms 見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
// 単純な方法
System.out.printf("単純な方法\n");
tm1 = System.currentTimeMillis();
hit = 0;
for (int i1 = 0; i1 < n; i1++) {
int sw = search_s(text1, pattern1[i1]);
if (sw < 0)
hit++;
}
tm2 = System.currentTimeMillis();
System.out.printf(" 探索時間： %d ms 見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
// BM 法
System.out.printf("BM 法\n");
tm1 = System.currentTimeMillis();
hit = 0;
for (int i1 = 0; i1 < n; i1++) {
int sw = search_BM(text1, pattern1[i1]);
if (sw < 0)
hit++;
}
tm2 = System.currentTimeMillis();
System.out.printf(" 探索時間： %d ms 見つからなかったパターン数： %d\n", (int)(tm2-tm1), hit);
}
/****************************************/
/* 単純な探索 */
/* text : テキスト */
/* ptn : 探索パターン */
/* return : 発見位置(失敗したら-1) */
/****************************************/
static int search_s(char text[], char ptn[])
{
int s = -1;
int len = text.length - ptn.length;
for (int i1 = 0; i1 < len; i1++) {
int k = i1;
int sw = 1;
for (int i2 = 0; i2 < ptn.length; i2++) {
if (ptn[i2] != text[k]) {
sw = 0;
break;
}
else
k++;
}
if (sw > 0) {
s = i1;
break;
}
}
return s;
}
/****************************************/
/* BM 法 */
/* text : テキスト */
/* ptn : 探索パターン */
/* return : 発見位置(失敗したら-1) */
/****************************************/
static int search_BM(char text[], char ptn[])
{
int len_t = text.length;
int len_p = ptn.length;
// ずらし幅テーブル
int step[] = new int [255];
for (int i1 = 0; i1 < 255; i1++)
step[i1] = -1;
for (int i1 = len_p-1; i1 >= 0; i1--) {
if (step[(int)ptn[i1]] < 0)
step[(int)ptn[i1]] = len_p - 1 - i1;
}
// 実行
int s = -1;
int k = len_p - 1;
while (k < len_t) {
int k1 = k;
int k2 = len_p - 1;
int sw = 1;
while (k2 >= 0) {
if (ptn[k2] != text[k1]) {
if (step[(int)text[k1]] < 0) // text[k1] がパターンに含まれない
k += len_p;
else { // text[k1] がパターンに含まれる
int k3 = step[(int)text[k1]];
int k4 = len_p - k2;
if (k3 > k4)
k = k1 + k3;
else
k = k1 + k4;
}
sw = 0;
break;
}
else {
k1--;
k2--;
}
}
if (sw > 0) {
s = k - len_p + 1;
break;
}
}
return s;
}
}