25

英数字の文字列があり、整数だけでパターンの繰り返しをチェックしたいと思います。そして、それらは継続的でなければなりません。

例

  1. 12341234q1234が繰り返されていることを教えてください。
  2. 1234qwe1234は、 1234が連続していないため、繰り返され ていることを教えてはなりません。
  3. 12121212は、繰り返されていることがわかる最初のセットであるため、 12が繰り返されているものとして扱う必要があります。しかし、 12の前に繰り返されるセットとして1212を見つけるアルゴリズムがある場合は、1212で再度手順を実行する必要があると思います。

私が思ったのは、整数部分を繰り返し( <= '0' && >= '9')て別ので比較することで格納できるということでしたStringBuilder。次に、文字列に対してFFTを実行する方法について読みました。これは、繰り返されるパターンを示しています。しかし、JavaでFFTを実行して結果を探す方法がわかりません。また、信号処理を行わずにこれを実行しようと思っていました。KMPパターンマッチングについて読みましたが、それは特定の入力でのみ機能します。これを行う他の方法はありますか？

4

5 に答える 5

58

これを解決するために正規表現の助けを借りることができると思います。次のようなコードを検討してください。

String arr[] = {"12341234abc", "1234foo1234", "12121212", "111111111", "1a1212b123123c12341234d1234512345"};
String regex = "(\\d+?)\\1";
Pattern p = Pattern.compile(regex);
for (String elem : arr) {
    boolean noMatchFound = true;
    Matcher matcher = p.matcher(elem);
    while (matcher.find()) {
        noMatchFound = false;
        System.out.println(elem + " got repeated: " + matcher.group(1));
    }
    if (noMatchFound) {
        System.out.println(elem + " has no repeation");
    }
}

出力：

abc12341234abc got repeated: 1234
1234foo1234 has no repeation
12121212 got repeated: 12
12121212 got repeated: 12
111111111 got repeated: 1
111111111 got repeated: 1
111111111 got repeated: 1
111111111 got repeated: 1
1a1212b123123c12341234d1234512345 got repeated: 12
1a1212b123123c12341234d1234512345 got repeated: 123
1a1212b123123c12341234d1234512345 got repeated: 1234
1a1212b123123c12341234d1234512345 got repeated: 12345

説明：

使用されている正規表現は(\\d+?)\\1どこにありますか

\\d        - means a numerical digit
\\d+       - means 1 or more occurrences of a digit
\\d+?      - means reluctant (non-greedy) match of 1 OR more digits
( and )    - to group the above regex into group # 1
\\1        - means back reference to group # 1
(\\d+?)\\1 - repeat the group # 1 immediately after group # 1
于 2012-04-23T19:26:46.930 に答える
7

あなたがRegularExpressions（RegEx）に精通しているかどうかはわかりませんが、このコードは機能します

String str = "12341234qwe";
String rep = str.replaceAll(".*(.+)\\1.*","$1");
if (rep.equals(str))
    System.out.println(str+" has no repition");
else
    System.out.println(str+" has repition "+rep);
str = "1234qwe1234";
rep = str.replaceAll(".*(.+)\\1.*","$1");
if (rep.equals(str))
    System.out.println(str+" has no repition");
else
    System.out.println(str+" has repition "+rep);

チュートリアルは次のとおりです：http：//docs.oracle.com/javase/tutorial/essential/regex/

于 2012-04-23T19:20:21.593 に答える
6

私の理論では、接尾辞木と呼ばれるデータ構造を使用して、目的を達成できます。

最初の文字列を調べて、連続する各数字シーケンスを収集し、その接尾辞ツリーを構築します。あなたの例では、次のようになります（最初の4つのサフィックスの場合）：

                  R - root
      |         |          |         |
      |         |          |         |
      |         |          |         | 
  12341234$  2341234$   341234$     41234$

さて、次の接尾辞は1234$になります。ただし、挿入すると、最初のサフィックスのプレフィックス1234と一致することがわかります。カウンターは並列に保持され、サフィックスがツリーに追加されるたびにインクリメントされます。

各ステップで、カウンターを、挿入される現在のサフィックスとそれが一致するサブストリングとの間の一致の長さと比較します。一致の長さがカウンターの倍数である場合、繰り返しがあります。

上記の場合、1234 $を挿入するまでにカウンターは4（0から開始）になり、プレフィックス12341234 $との一致の長さも4になるため、1234が繰り返されます。

于 2012-04-23T19:44:55.157 に答える
3

まず、パターンのいくつかのルールを定義する必要があります。パターンの長さが任意である場合は、int値の格納（パターンの構築）を開始し、最初に繰り返されるintでの繰り返しのチェックを開始する必要があります。

この場合：1234123q 1234パターンを作成しているので、1が繰り返されるので、それを保存し続け、次の値との比較を開始する必要があります。

パターン内の繰り返しをどのように処理しますか？

場合：123124123124

パターン123124が2回繰り返されます。繰り返しとして登録する必要がありますか、それとも123！= 124なので最初の4で停止する必要がありますか？

これらのケースを有効な繰り返しとして登録することを選択した場合は、並列パターンの作成を開始して、それらを構築し続けるときに、sime時にチェックする必要があります。

最初のケース（最初の繰り返されない値で停止する）は単純です。2番目のケースは、構築とチェックを同時に行うための多数の並列パターンを生成します。

ストリームの最後に到達したら、Stringが提供する既存のメソッドを使用して検索を実行できます。

于 2012-04-23T19:27:13.030 に答える
-5

ApacheCommonsLang。org.apache.commons.lang.StringUtils特定の部分文字列の出現をカウントするメソッドを持つクラスがあります。すでに存在しているため、独自のソリューションを作成する代わりに直接使用できます。

//First parameter is the string to find and second param is the String to search.
StringUtils.CountMatches("1234","12341234");
于 2012-04-23T19:29:20.377 に答える