android - 如何在不同语言的给定文本文件中搜索字符串

Question

我想为音乐系统应用程序开发模式搜索算法，该应用程序搜索给定的关键字并播放其文本文件包含给定关键字的音乐。现在有很多模式搜索算法可以有效地做到这一点(例如:KMP，散列(可能会出错)等)。但我的主要问题是整个数据库使用的语言不是英语(具体来说是“印地语”)。现在用户以“印地语”语言输入给定的关键字，我想在也包含“印地语”语言的数据库中进行搜索。我主要关心的是如何在这个数据库中高效地搜索？

我认为我们不能为非英语语言做KMP算法，因为我们使用的ascii字符只包含英文字母和其他数字字母，但不包含其他语言的字母。所以，请告诉我如何才能继续，因为我无法获得解决方案或告诉我我的想法是错误的？

Answer 1

KMP 算法不基于字母表，它使用给定模式和文本中的字符。此外，在 Java 等语言中，字符串使用 UTF-8 编码，因此您可以使用任何您喜欢的语言，并且算法可以正常工作，在其他语言中，您需要明确选择编码。在这里，我给出了使用 KMP 和非 ascii 字符集的 Ideone 示例的链接。 KMP algorithm

    /* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
    int[] f;
    public void dfa(String pattern) {
        int m = pattern.length();
        f = new int[m+1];
        f[0] = 0;
        f[1] = 0;
        for(int i=2; i<=m; i++) {
            int j = f[i-1];
            for(;;) {
                if(pattern.charAt(j) == pattern.charAt(i-1)) {
                    f[i] = j +1;
                    break;
                }
                if(j==0) {
                    f[i] = 0;
                    break;
                }
                j = f[j];
            }
        }
    }

    public int match(String text, String pattern) {
        dfa(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        int j = 0;
        for(;;) {
            if(i == n) break;
            if(text.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
                if(j == m) return i;
            }
            else if(j > 0) j =f[j];
            else i++;
        }
        return -1;
    }

    public static void main(String[] args) {
        Ideone kmp = new Ideone();
        String text = "AĄĘĆABA";
        String pattern = "ĄĘĆ";
        System.out.println(kmp.match(text, pattern));
    }
}