Leetcode/StringPatternMatch.h at master · RiceReallyGood/Leetcode · GitHub

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
55
56
57
58
59
60
61
62
63
64
65
#include <string>
#include <vector>
using namespace std;

class Solution
{
  public:
    int numMatchingSubseq(string S, vector<string> &words)
    {
        int count = 0;
        if (S.empty())
        {
            for (string &word : words)
            {
                if (word.empty())
                    ++count;
            }
            return count;
        }
        for (string &word : words)
        {
            if (word.empty())
                continue;
            int *next = findNext(word);
            int wlen = word.size(), slen = S.size();
            int i = 0, j = 0;
            while (i < wlen && j < slen)
            {
                if (i == -1 || word[i] == S[j])
                {
                    ++i;
                    ++j;
                }
                else
                    i = next[i];
            }
            if (i == word.size())
                ++count;
            delete[] next;
        }
        return count;
    }

    int *findNext(string &pattern)
    {
        int len = pattern.size();
        if (len == 0)
            return NULL;
        int *next = new int[len];
        next[0] = -1;
        int i = 0, k = -1;
        while (i < len - 1)
        {
            while (k >= 0 && pattern[i] != pattern[k])
                k = next[k];
            ++i;
            ++k;
            if (pattern[i] == pattern[k])
                next[i] = next[k];
            else
                next[i] = k;
        }
        return next;
    }
};