算法——字符串

引言

本文整理了常见的字符串相关算法，方便以后查阅。算法相关的文章均收录于<算法系列文章>。

字符串匹配

接口：

package bbm.match;

import java.util.List;

/**
 * @author bbm
 */
public interface StringMatcher {
    List<Integer> match(String string, String pattern);
}

测试：

package bbm.match;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * @author bbm
 */
class StringMatcherTest {

    @Test
    public void testNative() {
        StringMatcher stringMatcher = new NativeStringMatcher();
        List<Character> chars = Arrays.asList('1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'x');
        for (int loop = 0; loop < 10000; loop++) {
            StringBuilder stringBuilder = new StringBuilder();
            Random random = new Random(System.currentTimeMillis());
            for (int i = 0; i < 100; i++) {
                int index = random.nextInt(chars.size());
                stringBuilder.append(chars.get(index));
            }
            String string = stringBuilder.toString();
            int start = random.nextInt(100);
            int end = start + random.nextInt(100 - start);
            String patternString = string.substring(start, end);
            Pattern pattern = Pattern.compile(patternString);
            Matcher matcher = pattern.matcher(string);
            List<Integer> result = new ArrayList<>();
            while (matcher.find()) {
                result.add(matcher.start());
            }
            List<Integer> myResult = stringMatcher.match(string, patternString);
            try {
                Assertions.assertEquals(result.size(), myResult.size());
                for (int i = 0; i < result.size(); i++) {
                    Assertions.assertEquals(result.get(i), myResult.get(i));
                }
            } catch (Throwable e) {
                e.printStackTrace();
            }
        }
    }
}

朴素算法

package bbm.match;

import java.util.LinkedList;
import java.util.List;

/**
 * @author bbm
 */
public class NativeStringMatcher implements StringMatcher {
    @Override
    public List<Integer> match(String string, String pattern) {
        List<Integer> result = new LinkedList<>();
        for (int i = 0; i < string.length() - pattern.length() + 1; i++) {
            boolean match = true;
            for (int j = 0; j < pattern.length(); j++) {
                if (pattern.charAt(j) != string.charAt(i + j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                result.add(i);
            }
        }
        return result;
    }
}

状态机

package bbm.match;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 需要根据目标字符串构建状态机，从目标字符串中找到所有出现的字符，为每个字符进行编号，然后构建 (patternLength + 1) * 字符集数量 的状态
 * 转移表，构建状态转移表的一般思路是，假设 x 为 pattern 中的任意下标，stateMap[x][x + 1] = x+1 ，此时，我们要
 * 计算 "pattern[0, x] + y" 的后缀和 pattern[0, x+1] 的最长前缀，其中 y 恒不等于 pattern[x+1]，得到这个最大前缀 maxPrefix 之后，
 * stateMap[x][y] = maxPrefix.length
 *
 * 初始化时间复杂度：O（m*字符集数量）
 * 匹配时间复杂度：O(n)
 *
 * @author bbm
 */
public class StateMachineStringMatcher implements StringMatcher {

    private int[][] stateMap;
    private Map<Character, Integer> characters = new HashMap<>();

    public StateMachineStringMatcher(String pattern) {
        int index = 0;
        if (!pattern.isEmpty()) {
            for (int i = 0; i < pattern.length(); i++) {
                if (!characters.containsKey(pattern.charAt(i))) {
                    characters.put(pattern.charAt(i), index++);
                }
            }
            stateMap = new int[pattern.length() + 1][characters.size()];
            for (int i = 0; i < pattern.length() + 1; i++) {
                String sub = i < pattern.length() ? pattern.substring(0, i) : pattern;
                int rightIndex = -1;
                if (i < pattern.length()) {
                    rightIndex = characters.get(pattern.charAt(i));
                    stateMap[i][rightIndex] = i + 1;
                }
                for (Map.Entry<Character, Integer> entry: characters.entrySet()) {
                    if (!entry.getValue().equals(rightIndex)) {
                        for (int j = i + 1; j > 0; j--) {
                            String temp = sub + entry.getKey();
                            String prefix = j < pattern.length() ? pattern.substring(0, j) : pattern;
                            if (temp.endsWith(prefix)) {
                                stateMap[i][entry.getValue()] = Math.min(j, pattern.length());
                                break;
                            }
                        }
                    }
                }
            }
        } else {
            stateMap = null;
        }
    }

    @Override
    public List<Integer> match(String string, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (stateMap == null) {
            for (int i = 0; i < string.length() + 1; i++) {
                result.add(i);
            }
        } else {
            int state = 0;
            for (int i = 0; i < string.length(); i++) {
                if (characters.containsKey(string.charAt(i))) {
                    state = stateMap[state][characters.get(string.charAt(i))];
                } else {
                    state = 0;
                }
                if (state == pattern.length()) {
                    result.add(i - pattern.length() + 1);
                }
            }
        }
        return result;
    }
}

参考内容

[1] 《算法导论》