###前提・実現したいこと
パターン検索のプログラムですが、
入力
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/ツール等のバージョンなど)
より詳細な情報
回答2件
あなたの回答
tips
プレビュー