c - 排列字符串以使模式匹配

Question

问题是计算字符串 B 有多少种排列具有等效模式到更大的字符串 A。例如，如果 A="aabbccd" 和 B="xx"，那么它应该打印 3，因为 "aa"、"bb"、"cc" > 是 A 的所有子字符串，与 B 具有相同的模式。

我尝试将子字符串作为数字传递，例如 xx 变为 "11" 并对字符串 A 执行相同的操作，但是我仍然无法让它工作。有任何想法吗？长度最大可达 10^7。

这是更改模式的代码:

void transform(int* dest, char* original, int len) {
    int j=1;
    Al[original[0]-'a']=j;
    dest[0]=j;
    j++;
    for (int i=1;i<len;i++) {
        if (Al[original[i]-'a']==0) 
            Al[original[i]-'a']=j++;
        dest[i]=Al[original[i]-'a'];
    }
}

Answer 1

概念:使用正则表达式

您需要以下正则表达式(\\w)\\1{(REPETITIONS-1)}
我不了解 C，但 Java 提供了一个库来编译 RegEx 模式。这是一个实现您想要的类:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class StringPatternPermutation {
    public static void main(String[] args) {
        int REPETITIONS = 3;
        String REGEX = "(\\w)\\1{" + (REPETITIONS-1) + "}";
        String INPUT = "abbbbbbccddeffff";

        Pattern p = Pattern.compile(REGEX);
        Matcher m = p.matcher(INPUT); 

        int count = 0;
        while(m.find()){
            String match = m.group();
            System.out.println(match);
            count++;
        }

        System.out.println(count);
    }
}

这是对上面代码的测试:https://ideone.com/5nztaa
这是一个用于测试任何正则表达式的有用网站:https://regexr.com/