find occurrences of t in s where '?'s are automatically matched with any character res[i + m - 1] = sum_j=0 to m - 1_{s[i + j] * t[j] * (s[i + j] - t[j])^2
| 57 | //find occurrences of t in s where '?'s are automatically matched with any character |
| 58 | //res[i + m - 1] = sum_j=0 to m - 1_{s[i + j] * t[j] * (s[i + j] - t[j])^2 |
| 59 | vector<int> string_matching(string &s, string &t) { |
| 60 | int n = s.size(), m = t.size(); |
| 61 | vector<int> s1(n), s2(n), s3(n); |
| 62 | for(int i = 0; i < n; i++) s1[i] = s[i] == '?' ? 0 : s[i] - 'a' + 1; //assign any non zero number for non '?'s |
| 63 | for(int i = 0; i < n; i++) s2[i] = s1[i] * s1[i]; |
| 64 | for(int i = 0; i < n; i++) s3[i] = s1[i] * s2[i]; |
| 65 | vector<int> t1(m), t2(m), t3(m); |
| 66 | for(int i = 0; i < m; i++) t1[i] = t[i] == '?' ? 0 : t[i] - 'a' + 1; |
| 67 | for(int i = 0; i < m; i++) t2[i] = t1[i] * t1[i]; |
| 68 | for(int i = 0; i < m; i++) t3[i] = t1[i] * t2[i]; |
| 69 | reverse(t1.begin(), t1.end()); |
| 70 | reverse(t2.begin(), t2.end()); |
| 71 | reverse(t3.begin(), t3.end()); |
| 72 | vector<int> s1t3 = multiply(s1, t3); |
| 73 | vector<int> s2t2 = multiply(s2, t2); |
| 74 | vector<int> s3t1 = multiply(s3, t1); |
| 75 | vector<int> res(n); |
| 76 | for(int i = 0; i < n; i++) res[i] = s1t3[i] - s2t2[i] * 2 + s3t1[i]; |
| 77 | vector<int> oc; |
| 78 | for(int i = m - 1; i < n; i++) if(res[i] == 0) oc.push_back(i - m + 1); |
| 79 | return oc; |
| 80 | } |
| 81 | int32_t main() { |
| 82 | ios_base::sync_with_stdio(0); |
| 83 | int t; |