Untitled
unknown
c_cpp
a year ago
1.4 kB
4
Indexable
class Solution { public: vector<int> preprocess(string s){ int n = s.size(), prefix_len = 0, i = 1; vector<int>next = {0}; while(i < n){ if(s[prefix_len] == s[i]){//Find common between prefix and suffix prefix_len++; next.push_back(prefix_len); i++; } else{ if(prefix_len > 0)//Go backward prefix_len = next[prefix_len-1]; else{ next.push_back(0); i++; } } } return next; } int strStr(string source, string target) { int m = source.size(), n = target.size(); if(source == target) return 0; vector<int>next = preprocess(target); int i = 0, j = 0;//i: source, j: target while(i < m){ if(source[i] == target[j]){//Match i++; j++; } else if(j > 0)//Go backward to find common prefix and suffix j = next[j-1]; else//Does not match at first char i++; if(j == n) return i-j; } return -1; } //KMP Algorithm //Time O(m+n) //Space O(n) };
Editor is loading...
Leave a Comment