8

これを解決する方法がわかりません：

2 つの文字列 (1 つはパターンを表し、もう 1 つはランダムな文字列) が与えられた場合、そのパターンが最初の文字列と一致するかどうかを判断します

元：

string1: "aaba"
string2: "catcatdogcat"

したがって、string1 と string2 はパターン マッチングされます。

対 string2 の場合、"catcatcatcat"これはパターン一致しません。

任意のパターンと文字列に対してこれを行います。

私はそれが再帰であることを知っていますが、私はかなり行き詰まっています...これを解決する方法

4

3 に答える 3

2

わかりました、これの再帰を説明しようと思いますが、正しいように聞こえますが、テストする機会がありません (自宅ではありません)。

ベクトル v['アルファベットのサイズ'] を取得します。ここで、v[i] = string2 からの文字数 = 文字列 1 からの文字 i です。

あなたの場合、最終的には v['a'] = 3, v[b] =3; です。

ベクトルを 1 で初期化します。

rec 関数の場合:

string1 から最初の文字を取得します。from string2 を表すのは、string2 で始まり string2+v['a'] で終わる文字列です。これは「c」です。これが今まで有効な解決策であるかどうかを確認すると、有効です。

次に、rec( string1 + 1 ) に入り、文字 a を再び入力します。v['a'] はまだ = 1 であるため、2 番目の a を = 'a' として取得します。これが有効なソリューションであるかどうかを確認します。これは、最初の a を既に 'c' として定義しているためではありません。再帰に戻り、v['a'] をインクリメントします。

string1 の最初の文字を取ります: a; 'ca' である string2 から表します (現在は v['a'] = 2 ) が有効かどうかを確認します。rec ( string1 +1 );

など... v['a'] = 3 および v['b'] = 3 に到達する時点で。次に、 rec 関数を使用して解決策を見つけます。

私はインタラクティブ関数で実装する方が簡単だと思いますが、あなたは再帰について何か言いました。

于 2013-10-22T18:49:44.083 に答える
2

一意の文字の数を取ります。次に、次の制約を使用して、各文字の可能な長さのすべての組み合わせを反復処理します。

  1. 合計 (文字の長さ * 文字の出現回数) は string2 の長さでなければなりません
  2. 各長さは少なくとも 1 でなければなりません

つまり、2 つの一意の文字と文字列の長さが 4 の場合、考えられる長さは次のとおりです。

(1, 3) および (2, 2)

ここからは簡単です。各文字の長さがわかっているので、一意の文字ごとに、その文字が特定の文字列に対して表す必要がある文字列を見つけることができます。次に、各文字をそれが表す必要がある文字列にマッピングすることが問題であり、文字が以前のインスタンスと一致しなかった文字列に対応する場合はいつでも一致しません。

あなたの例：

string1: "aaba"
string2: "catcatdogcat"

ここでは、長さが (3, 3) の反復についてです。a の長さが 3 であることがわかっているので、a の最初の繰り返しは "cat" でなければならないことがわかります。次に、次の a は "cat" に対応します (まだ一致があります)。次に、次の 3 は b に対応する必要があります。これは最初の b であるため、任意の 3 文字に一致します。最後に a を cat に再度一致させれば完了です。

@MartijnCourteauxコメントで概説されているようにa、b、cを一意にしたい場合（そしてあなたの質問でもう一度読んでください）、最後に共通の値があるかどうかマップを確認できます。共通の値がある場合あなたにはマッチがありません。

ANY 反復で一致する場合、文字列はパターンと一致します。すべての反復で一致がない場合にのみ、一致はありません。

于 2013-10-22T19:18:30.093 に答える
1

これは非常に簡単に実現できます。

正規表現は行く方法です。正規表現には、 backreferenceと呼ばれるものがあります。後方参照はまったく同じ文字列と一致する必要があります。前述の一致グループは既に一致しています。つまり、正規表現はor^([ab])\\1$のようなすべての文字列に一致します。最初のグループは a または b のいずれかに一致しますが、後方参照は同じものに一致する必要があり、一致グループ (この場合は "1") が一致します。aabb

したがって、必要なことは次のとおりです。文字列ベースのパターンを正規表現パターンに変換します。

例：

String regex = "^([a-z]+)\\1([a-z]+)\\1$";
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher("catcatdogcat");

   if (m.matches()){
     System.out.println("matches!");
     System.out.println(m.group(0));
     System.out.println(m.group(1));
     System.out.println(m.group(2));

   }else{
    System.out.println("no matches!");
   }

生成:

matches!
catcatdogcat
cat
dog

これは、指定された文字列「catcatdogcat」と正確に一致しますが、グループ 1 beeing 「cat」と一致し、グループ 2 beeing 「dog」と一致します。

あなたが今しなければならないことは次のとおりです。

  • 文字列パターンを 1 文字ずつチェックする関数を作成しますaaba。
  • 文字の最初の出現: それを置き換えて([a-z]+)、そのマッチグループの番号を書き留めます (配列、ハッシュマップなど)
  • それ以降の文字の出現: で置き換えます\\1(文字の記録された番号が 1 の場合)
  • ^結果をandでラップし$ます。

最後に、文字列aabaが変換され^([a-z]+)\\1([a-z]+)\\1$、ニーズに応えます。パターンabccbaは正規表現になります^([a-z]+)([a-z]+)([a-z]+)\\3\\2\\1$

最後にマッチャーを使用して、指定された文字列をチェックします。

この例では小文字のみを想定していますが、拡張できます。

ただし、「+」を保持することが重要です。「*」では長さの一致がゼロになるため、正規表現はほぼ常に一致します。

言及された2番目の例：

import java.util.regex.*;

public class HelloWorld {
  public static void main(String[] args) {
   String regex = "^([a-z]+)([a-z]+)([a-z]+)\\3\\2\\1$";
   Pattern p = Pattern.compile(regex);
   Matcher m = p.matcher("catdogcowcowdogcat");

   if (m.matches()){
     System.out.println("matches!");
     System.out.println(m.group(0));
     System.out.println(m.group(1));
     System.out.println(m.group(2));
     System.out.println(m.group(3));

   }else{
    System.out.println("no matches!");
   }
  }
}

生成:

matches!
catdogcowcowdogcat
cat
dog
cow

編集：必要に応じて（要件に100％一致しない場合でも-コメントを参照してください）：

public static String convertToRegex(String pattern){
    String regex = "";
    Map<Character, Integer> refs = new HashMap<Character, Integer>();
    Integer i=1;
    for (Character c : pattern.toCharArray()){
      if (refs.containsKey(c)){
         //known.
         regex += "\\" + refs.get(c);
      }else{
         //unknown
         regex += "([a-z]+)";
         refs.put(c, i++);
      }
    }

    return "^" + regex + "$";
  }
于 2013-10-22T19:44:27.227 に答える