leetcode

0 class Solution {

1 vector<int> needle, lps;

2

3 void computeKMPTable(vector<int> needle) {

4 lps.resize(needle.size(), 0);

5

6 for (int len = 0, j = 1; j < size(needle);) {

7 if (needle[j] == needle[len])

8 lps[j++] = ++len;

9 else if (len)

10 len = lps[len - 1];

11 else

12 lps[j++] = 0;

13 }

14 }

15

16 bool kmpSearch(TreeNode *root, int j) {

17 if (j == size(needle)) return true;

18 if (!root) return false;

19 while (j > 0 && root->val != needle[j])

20 j = lps[j - 1];

21 if (root->val == needle[j]) j++;

22 return kmpSearch(root->left, j) || kmpSearch(root->right, j);

23 }

24

25 public:

26 bool isSubPath(ListNode *head, TreeNode *root) {

27 if (!head || !root) return false;

28

29 needle.resize(0);

30 for (ListNode *t = head; t; t = t->next)

31 needle.push_back(t->val);

32

33 computeKMPTable(needle);

34 return kmpSearch(root, 0);

35 }

36 };