0

I have an array of characters:

a b c x y d e f x y a b c t r e a b c

How can I find repetitive patterns of sizes 2 onwards?

The array needs to be traversed from the end. In the example I need to find patterns b c, a b, x y and patterns of sizes 3: a b c and x y z. Along with the indices of matching chars.

So far I have tried to traverse the array backwards and find patterns:

for (int size = 2; size < aLT.size(); size++) {
    for (int i = aLT.size() - 1; i >= 0; i--) {
        // code here
    }
}
4

3 回答 3

0 
int n = 2; // in your case 2 and 3
Map<String, List<Integer>> matches = new HashMap<String, List<Integer>>();
String charsString = new String( chars );
String current = null;
String rest = null;
for( int i = chars.length - n; i >= 0; i-- ) {
    current = charsString.substring( i, i + n );
    rest = charsString.substring( 0, i );
    int index = rest.indexOf( current );
    if( index > -1 ) {
        if( matches.containsKey( current ) ) {
            continue;
        }
        List<Integer> indices = new ArrayList<Integer>();
        indices.add( i );
        while( index > -1 ) {
            indices.add( index );
            index = rest.indexOf( current, index + 1 );
        }
        matches.put( current, indices );
    }
}

// print the results
for( Entry<String, List<Integer>> match : matches.entrySet() ) {
    System.out.println( match.getKey() + " with indices: " + match.getValue() );
}

输出是：

ab with indices: [16, 0, 10]
bc with indices: [17, 1, 11]
xy with indices: [8, 3]
于 2013-09-21T19:27:52.937 回答
0

这将完成这项工作，您可以将 patternSize 变量更改为您想要的任何值（远小于输入字符串的大小）：

它利用了String#contains()查找第一个字符串的子序列的方法。

    public static void main(String[] args) {
    int patternSize=4;
    String input = "abcxydefxyabctreabcabcx";
    Set<String> patterns = new TreeSet<String>();

    // test size n patterns
    for (int i=0; i<input.length()-patternSize; i++){
        String pattern = (String) input.subSequence(i, i+patternSize);
        String tester="";
        if (i>0 && i<input.length()-patternSize-1)
            tester = input.substring(0,i)+input.substring(i+patternSize);
        else if (i==0)
            tester = input.substring(i+patternSize);
        else if (i==input.length()-patternSize-1)
            tester = input.substring(0,i);

        if (tester.contains(pattern)){
            patterns.add(pattern);
        }
    }   

    System.out.println("Size "+patternSize+" patterns finder");
    for(String aPattern : patterns){
        System.out.println("The pattern "+aPattern+" was found several times");
    }
}
于 2013-09-21T18:48:58.147 回答
0

这是一种可以执行您想要执行的操作的方法。如果您想通过更改 patternSize 和添加到集合中的字符串来查找不同大小的模式，您所要做的一切。目前我让它返回匹配数量的计数，但您可以轻松修改它以返回其他内容，例如匹配开始位置的索引或是否存在匹配的布尔值。

    public static int findPatterns(char[] charArray) {
    int patternSize = 2;
    Set<String> patterns = new HashSet<>();
    patterns.add("bc");
    patterns.add("ab");
    patterns.add("xy");
    int count = 0;
    if (charArray.length < patternSize) {
        return 0;
    }
    for (int i = 0; i < charArray.length - patternSize + 1; i++) {
        String pattern = "";
        for (int j = i; j < i + patternSize; j++) {
            pattern += charArray[j];
        }
        if (patterns.contains(pattern)) {
            count++;
        }
    }
    return count;
}
于 2013-09-21T20:00:30.033 回答