本文介绍 有趣的算法问题之字符串专辑

有趣的算法问题之字符串专辑

本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：jintianiloveu

字符串问题

字符串问题真的是经常遇到啊，小到匹配字符串，计算字符串相似度，大到海量数据统计搜索查询次数。好像都有字符串的身影。接下来就抛出几个厉害一点的字符串问题：

最长的无重复子字符串
这个问题的思想跟求取子数组的最大和相似。说白了就是遍历字符串，一个一个遍历，维护一个maxNoRepeat的string，每次遍历添加到这个string里面去，根据HashTable判断是否在前面出现过，如果出现那么就放弃这个maxNoRepeat，同时将其复制给一个tempString，这个是我们要保存的记录前面一次的最长不重复子串，放弃当前的maxNoRepeat之后，再将重复的字符串出现的位置后面的那一个开始复制给maxNoRepeat，继续遍历。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
typedef struct Hash{
    char c;
    int times;
    int lastPos;
};
string find_max_no_repeat(string a) {
    string maxNoRepeat = "";
    string tmp = "";
    int n = 52;
    Hash *HashTable = new Hash[n];
    for (int i = 0; i < a.size(); ++i) {
        // according to current char, update hash table
        int pos = (bool) islower(a[i]) ? (a[i] - 'a') : (a[i] - 'A' + n/2);
        if (HashTable[pos].times == 1) {
            // indicates a[i] exist
            // be care of substring usage, begin index and len
            auto lastPos = HashTable[pos].lastPos;
            maxNoRepeat = a.substr(lastPos + 1, i - lastPos);
            tmp = maxNoRepeat.size() > tmp.size()? maxNoRepeat: tmp;
            // clear HashTable, all char before last pos in a will be clear
            for (int k = 0; k < HashTable[pos].lastPos; ++k) {
                int tmpChar = a[k];
                int aPos = (bool) islower(tmpChar) ? (tmpChar - 'a') : (tmpChar - 'A' + n/2);
                HashTable[aPos].lastPos = 0;
                HashTable[aPos].times = 0;
            }
            // remember to update last pos
            HashTable[pos].lastPos = i;
        } else {
            maxNoRepeat += a[i];
            cout << maxNoRepeat << endl;
            HashTable[pos].times = 1;
            HashTable[pos].lastPos = i;
        }
    }
    maxNoRepeat = maxNoRepeat.size() > tmp.size()? maxNoRepeat: tmp;
    return maxNoRepeat;
}
int main()
{
    string a = "hgieophtpuaopwhrguf";
    cout << a << endl;
    string b = find_max_no_repeat(a);
    cout << b << endl;
}

看上去这个简单吗？简单你妈，老子骂了一天你敢信？我曹，这么说吧，没有看任何参考，完全自己骂出来的。这个问题的思路非常简单，就是维护一个中间值，遍历一遍字符串，维护一个哈希表，这个哈希表就是查找下一个字符是否出现过，如果出现过，那么就对字符进行截取，从上一次出现的位置截取，同时把它复制给中间值。但是别忘了还要维护哈希表，维护就是把每一次新增的字符之前的也就是最近一次重复的统统归于零，与此同时要更新一下当前重复的上次的位置。如此便可破此题。
好吧，这是我写过最牛逼算法了，其实如果你直接手撸实现的话会有无数的坑，总结一下：

  1. 维护HashTable的时候，我是直接delete []，然后new，试图全部抹掉重新来，发现尼玛不行，这一点没有考虑抽取全，当前的字符串子串的HashTable还是不能变；
  2. HashTable找到一个重复元素时，要更新HashTable该元素的上一次位置，也就是当前位置，因为你重复之后你就需要截取字符，截取字符如果不改变当前重复字符的位置的话，还是上一次重复的位置，下一次截取就会出错。

好了，坑已踩完。