質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

354閲覧

パターン検索での該当部のif文の役割を解説して頂ける方おられませんか?

gyro16

総合スコア89

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2017/07/04 01:15

編集2017/07/04 02:56

###前提・実現したいこと

パターン検索のプログラムですが、

入力
3 3
010
001
010
2 2
10
01
出力
0 1

入力されたものの中から
"010"
"001"
"010"

検索パターンを探す。

上の例なら、
2行2列の
"10"
"01"
パターンが何行、 何列目にあるかを回答するプログラムです。
0行 1列目に
"10"
"01"がある、という判定をする。

と判定するパターン検索プログラムで、
入力されるものt と検索パターンp は、

制約は、行は 1 以上 1000 以下、
列も 1 以上 1000以下です。

大きな入力と大きなパターンが与えられる時、解答時間制限でアウトになりますが、
int clen = p.length();
int pstlen = stPre + p.length();
if(st >= pstlen - retPre && st < pstlen){
clen -= pstlen - st;
}

このif文があると、解答時間内に正当できます。
このif文は何をしているのですか、解説していただけたら幸いです。

stは、検索範囲をループする変数
stPreは、検索開始位置
retPreは、検索終了位置 でいいのかな。
pstlenは、検索開始位置から検索文字列の長さまでの長さ
pstlen - retPreは、検索終了位置から残りの検索文字列までの長さ でいいのかな。

###発生している問題・エラーメッセージ

エラーメッセージ

###該当のソースコード

java

1import java.util.*; 2 3public class Algo50{ 4 public static void main(String[] args){ 5 6 Scanner scan = new Scanner(System.in); 7 8 int h = scan.nextInt(); 9 int w = scan.nextInt(); 10 String[] t = new String[h]; 11 for(int i = 0; i < h; i++) 12 t[i] = scan.next(); 13 14 int r = scan.nextInt(); 15 int c = scan.nextInt(); 16 String[] p = new String[r]; 17 for(int i = 0; i < r; i++) 18 p[i] = scan.next(); 19 20 PtFind f = new PtFind(t, p, false); 21 22 scan.close(); 23 System.exit(0); 24 } 25} 26 27class PtFind{ 28 boolean debug; 29 30 public PtFind(String[] t, String[] p, boolean d){ 31 debug = d; 32 33 boolean[][] jg = new boolean[t.length - p.length + 1][t[0].length() - p[0].length() + 1]; 34 //lengthは配列の要素数、length()は文字列数 35 for(int y = 0; y < jg.length; y++) 36 for(int x = 0; x < jg[0].length; x++) 37 jg[y][x] = true; //trueを代入する 38 39 for(int r = 0; r < p.length; r++){ 40 StFind stf = new StFind(p[r], d); 41 for(int y = 0; y < jg.length; y++){ 42 boolean[] result = new boolean[jg[0].length]; 43 stf.find(t[y+r], p[r], result); 44 for(int x = 0; x < jg[0].length; x++) 45 jg[y][x] &= result[x]; 46 //a &= bは、a = a & b 47 } 48 } 49 50 for(int y = 0; y < jg.length; y++) 51 for(int x = 0; x < jg[0].length; x++) 52 if(jg[y][x]) 53 System.out.println(y + " " + x); 54 } 55} 56 57// 58class StFind{ 59 boolean debug; 60 int[] msft; 61 int[] sft = new int[Character.MAX_CODE_POINT]; 62 63 public StFind(String p, boolean d){ 64 debug = d; 65 createMatchPt(p); 66 } 67 68 public void find(String t, String p, boolean[] result){ 69 int x = 0; 70 for(int st = 0; st < t.length() - p.length() + 1;){ 71 if((x = isBaEqual(t, p, st)) == p.length()) 72 result[st] = true; 73 st += msft[x]; 74 } 75 } 76 77 private void createMatchPt(String p){ 78 msft = new int[p.length() + 1]; 79 msft[0] = p.length(); 80 81 for(int sft = p.length(); sft > 0; sft--){ 82 for(int m = 1; m < msft.length; m++){ 83 if(m > p.length() - sft){ 84 msft[m] = sft; 85 continue; 86 } 87 if(p.charAt(p.length() - m) != p.charAt(p.length() - m- sft)){ 88 msft[m-1] = sft; 89 break; 90 }else if(m == p.length() -sft) 91 msft[m] = sft; 92 } 93 } 94 95 if(debug) 96 for(int i = 0; i < msft.length; i++) 97 System.out.println("--- " + i + " : " + msft[i]); 98 } 99 100 // 101 int stPre = 0; 102 int retPre = 0; 103 104 private int isBaEqual(String t, String p, int st){ 105 int clen = p.length(); 106 int pstlen = stPre + p.length(); 107 if(st >= pstlen - retPre && st < pstlen){ 108 clen -= pstlen - st; 109 } 110 for(int i = 0; i < clen; i++){ 111 if(t.charAt(p.length() - 1 - i + st) != p.charAt(p.length() - 1 - i)){ 112 stPre = st; 113 retPre = i; 114 return i; 115 } 116 } 117 stPre = st; 118 retPre = p.length(); 119 return p.length(); 120 } 121}

###試したこと
課題に対してアプローチしたことを記載してください

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tamy

2017/07/04 01:36

このJavaっぽいけどよくわからないコードを読んで変数の意味を理解した上で質問に回答しろというのは乱暴すぎると思うので,その辺をコード中のコメントで解説するなり変数名を工夫するなりしていただけたら幸いです.
swordone

2017/07/04 01:43

そもそも何をどう判定するプログラムなのかも読めないです。
ozwk

2017/07/04 01:56

おそらく、入力は検索元となる行列と検索する部分行列の2つで、出力は検出場所でしょうね
guest

回答2

0

自己解決

if文は消去法でした。
stが調べている文字数目、例えばpが10文字だった場合、stが5文字目なら5文字分調べる、stが6文字目なら4文字分調べる、…9文字目なら1文字分調べる、を調べれば合致するかを調べるというものでした。

投稿2017/07/04 04:22

編集2017/07/04 05:03
gyro16

総合スコア89

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

gyro16

2017/07/04 08:03

計算量を減らすifでした。 st文字列目まで合致していたら、残りの文字数分だけ合致しているかを調べる、というものでした。
gyro16

2017/07/28 07:38

stは検索範囲です。
guest

0

if文の効果がしりたければ、clen を表示すればよいのでは?

たぶんですが、10文字の中から8文字検索する場合、検索は10回じゃなくて、
1~8文字、2~9文字、3~10文字の3回に減らしたいってだけだと思いますけど。

投稿2017/07/04 03:02

momon-ga

総合スコア4820

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

momon-ga

2017/07/04 03:07

あ、ソースをまじめに読んだわけじゃなく、単純にclenを減らしてるのとループの終了条件だからって理由から推測しただけですので・・・
gyro16

2017/07/04 03:16

なるほど、納得しました。
momon-ga

2017/07/04 03:18

AOJ昔やってましたが、再開しようかな・・・
gyro16

2017/07/04 04:16

消去法でしたね。10文字で5文字目まで調べたら残り5文字部分、6文字目なら残り4文字分、…9文字目なら1文字分だけ調べれば合致するか分かるというものでした。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問