string - 在数组中找到第一个字符串匹配？

Question

我写了一个简单的字符串搜索算法，我想改进，我应该从哪里开始？

之所以要改简单的算法是:

1. pool 好像是个大数组
2. toSearch 中的字符串似乎是长字符串

代码如下:

var pool []string = []string{"st", "se", "go", "es", "per", "123", "abcd", "e", "2"}

func search(aStr string) (index int) {
    for i, s := range pool {
        if strings.Contains(aStr, s) {
            return i
        }
    }

    return -1
}

func main() {
    toSearch := []string{"string", "search", "algorithm", "best", "performance"}
    for _, s := range toSearch {
        idx := search(s)
        fmt.Printf("search %s in %d(%s)\n", s, idx, pool[idx])
    }
}

Answer 1

您可以使用一个特殊字符将所有字符串连接到 toSearch 数组中，比如 $，那么您的搜索字符串将变为 "string$search$algorithm$best$performance"，您可能还需要分配一个数组，如果您找到匹配项，它将记录您当前所在的字符串。

恐怕对于池数组，您将不得不一个一个地搜索上面创建的字符串。

降低复杂性的方法之一是对池数组的每个元素使用线性时间模式匹配算法，而不是您使用的二次时间模式匹配算法。

我已经发布了 3 个线性时间算法来搜索给定字符串中的模式，其中 2 个是确定性的，最后一个是非确定性的。

确定性和更标准的解决方案之一是使用 Knuth Morris Pratt algorithm尽管理解起来有点复杂，但您可以轻松地找到在线实现它的代码。它是线性时间，其中m是输入字符串的长度，n是模式的长度。

另一种确定性算法，也是我最喜欢的算法之一，它是 Z 算法更容易理解和实现，也是线性时间，它构造了所谓的 Z 数组，即用于轻松计算字符串中的模式匹配。您可以在 Z Algorithm 上查看此链接

如果要使用非确定性算法，可以使用Rabin Karp algorithm ，它需要散列(特别是 Rolling Hash 的概念)并且它最容易实现并且是线性时间。如果您检查使用散列得到的字符串是否由于冲突而正确或不正确，它也可以是确定性的，但在最坏的情况下，如果您使 rabin karp 算法具有确定性，它会产生二次复杂度。

我已经使用下面的 Z 算法编写了一个 C++ 代码:

#include<iostream>
#include<string>

using namespace std;

string s, temp;
int n, Z[1000];
int toSearchSize, poolSize, lookUpIndex[1000];
string toSearch[5] = {"string", "search", "algorithm", "best", "performance"};
string pool[9] = {"st", "se", "go", "es", "per", "123", "abcd", "e", "2"};

void joinString(){
    int idx = 0;
    for(int i = 0;i < toSearchSize;i++){
        s += toSearch[i];
        for(int j = idx;j <= idx+toSearch[i].size();j++) lookUpIndex[j] = i;
        s += "$";
        idx += toSearch[i].size()+1;
    }
    temp = s;
}

void zval(){
    int L = 0, R = 0;
    for(int i = 1;i<n;i++){
        if(i > R){
            L = R = i;
            while(R < n && s[R-L] == s[R]) R++;
            Z[i] = R-L;R--;
        }else{
            int b = R-i+1;
            if(Z[i-L] < b) Z[i] = Z[i-L];
            //else if(Z[i-L] > b) Z[i] = b;
            else{
                L = i;
                while(R < n && s[R-L] == s[R]) R++;
                Z[i] = R-L;R--;
            }
        }
    }
}

int main(){
    toSearchSize = 5, poolSize = 9;
    joinString();

    for(int i = 0;i < poolSize;i++){
        for(int j = 0;j < n;j++) Z[j] = 0;
        s = pool[i] + temp;
        n = s.size();
        zval();

        for(int j = pool[i].size();j < n;j++){
            if(Z[j] >= pool[i].size()){
                cout << "Match Found for : " << pool[i] << " in string : " << toSearch[lookUpIndex[j]] << endl;
            }
        }
    }

    return 0;
}

以上代码的输出:

Match Found for : st in string : string
Match Found for : st in string : best
Match Found for : se in string : search
Match Found for : go in string : algorithm
Match Found for : es in string : best
Match Found for : per in string : performance
Match Found for : e in string : search
Match Found for : e in string : best
Match Found for : e in string : performance
Match Found for : e in string : performance

Ideone 解决方案链接:http://ideone.com/UGJR3i