大きな2D配列の内部にある2D配列を見つける

Question

1行に1つの文字列しかないテストケースの問題を解決できます.1行に複数の文字列があると失敗します。例えば

：

テストケースタイプ1：

ビッグマトリックス：

7283455864 
6731158619 
8988242643 
3830589324 
2229505813 
5633845374 
6473530293 
7053106601 
0834282956 
4607924137 

小行列：9505が発生したとして

9505 
3845 
3530 

私はテストケースこれらの種類を渡しますビッグマトリクス内では最大でも1回です。

テストケースのタイプ：2

ビッグマトリックス：

7652157548860692421022503 
9283597467877865303553675 
4160389485250089289309493 
2583470721457150497569300 
3220130778636571709490905 
3588873017660047694725749 
9288991387848870159567061 
4840101673383478700737237 
8430916536880190158229898 
8986106490042260460547150 
2591460395957631878779378 
1816190871689680423501920 
0704047294563387014281341 
8544774664056811258209321 
9609294756392563447060526 
0170173859593369054590795 
6088985673796975810221577 
7738800757919472437622349 
5474120045253009653348388 
3930491401877849249410013 
1486477041403746396925337 
2955579022827592919878713 
2625547961868100985291514 
3673299809851325174555652 
4533398973801647859680907 

小行列：

5250 
1457 
8636 
7660 
7848 

I 5250（または小マトリクス内の他の行のテストケースのこれらの種類をフェイル）は、より大きい行列の同じ行の内部で2回以上出現する：

以下はコードi

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 


public class Solution { 

    public static void main(String[] args) { 

     HashMap<Integer,Integer> rowCol=new HashMap();  
     Scanner in = new Scanner(System.in); 
     int t = in.nextInt(); 
     for(int a0 = 0; a0 < t; a0++){ 
      //bigger array 
      int R = in.nextInt(); 
      int C = in.nextInt(); 
      String G[] = new String[R]; 
      for(int G_i=0; G_i < R; G_i++){ 
       G[G_i] = in.next(); 
      } 
      //smaller array 
      int r = in.nextInt(); 
      int c = in.nextInt(); 
      String P[] = new String[r]; 
      for(int P_i=0; P_i < r; P_i++){ 
       P[P_i] = in.next(); 
      } 

      for(int i = 0;i<R-r;i++)//obvious 
      { 
       for(int j = 0; j<r;j++)//obvious 
       { 
        //if string found put in map(row at which found,column at whch found) 
        if(G[i].indexOf(P[j])>=0)//string found 
        { 
         rowCol.put(i,G[i].indexOf(P[j])); 
        } 
       } 
      } 

      //now check if rows are consecutive(1,2,3) and columns are equal(1,1,1) 
      HashSet<Integer> mc = new HashSet<Integer>(rowCol.values());//if size==1 then same column 
      ArrayList<Integer> mr = new ArrayList<Integer>(rowCol.keySet()); 
      int count = 0; 
      for(int m = 0 ;m<mr.size()-1;m++)//checking if keys are consecutive 
      { 

       if(mr.get(m)+1==mr.get(m+1)) 
       { 
        count++;//how many values are same ,hw mny strings found at same index 
       } 
      } 

      //System.out.println(count+"+++++"+(mr.size()-1)); 
      //System.out.println(rowCol.values().size()+"==="+r); 

      if(mc.size()==1 && count==(mr.size()-1) && rowCol.keySet().size()==r)//all column same && all rows are consecutive && 
      { 
       System.out.println("YES"); 
      } 
      else 
      { 
       System.out.println("NO"); 
      } 


     } 


    } 
} 

Answer 1

あなたのロジックに問題があります。

for(int i = 0;i<R-r;i++)//obvious 
    { 
     for(int j = 0; j<r;j++)//obvious 
     { 
      //if string found put in map(row at which found,column at whch found) 
      if(G[i].indexOf(P[j])>=0)//string found 
      { 
       rowCol.put(i,G[i].indexOf(P[j])); 
      } 
     } 
    } 

これは、Gのすべての行を通過し、Pの行は、Gのラインに存在する場合、Pのすべての行は、それがマップに配置されます。

しかし、まず、のPの行がGの行にあると伝えますが、それはあなたにどの行を伝えないのですか。これは、既存の行列に似ているが行の順序が異なる小さな行列を探しているときにも失敗することを意味します。

第2に、Gの行に小さい行列の行が複数ある場合、下の行のインデックスがPから維持されます。つまり、同じ行に5250と7660の両方がある場合G、それは7660のちょうどインデックスを維持し、5250

ArrayList<Integer> mr = new ArrayList<Integer>(rowCol.keySet()); 

を無視するあなたは、連続したラインを確認するためにmrを使用しているが、あなたはHashMapから設定キーでそれを埋めています。これは注文が保証されないことを意味します - あなたは5,3,1,2,4の順番で行番号を得ることができます。

異なるロジックでプログラムを書く必要があります。すべての行のすべての場所を収集しようとしないでください。 Pの最初の行の位置を見つけ、残りが所定の位置にあるかどうかを直ちに確認します。 30行目のインデックスの15行目の最初の行が見つかったとし、2行目が31行目のインデックス15で3行目が32行目のインデックス15にあるかどうかを確認します。

すべて一致した場合は "YES"を、からはを返します。ループを続行しないでください。しかし、すべてが一致しない場合は、P [0]を探し続ける。

• Gの同じ行に複数のP [0]が存在する可能性があることに注意してください。一致が失敗した場合は、P [0] Gの次の行に移動します。
• 一致するものが見つからなかった場合は、ループの最後に "NO"を印刷できます。