3303. Find the Occurrence of First Almost Equal Substring
You are given two strings s and pattern.
A string x is called almost equal to y if you can change at most one character in x to make it identical to y.
Return the smallest starting index of a substring in s that is almost equal to pattern. If no such index exists, return -1.
A substring is a contiguous non-empty sequence of characters within a string.
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
| vector<int> zfunction(string s) {
int l = 0, r = 0, n = s.size();
vector<int> z(n);
for(int i = 1; i < n; i++) {
if(i > r) {
l = r = i;
while(r < n and s[r-l] == s[r]) r++;
z[i] = r - l;
r--;
} else {
int k = i - l;
if(z[k] < r - i + 1) z[i] = z[k];
else {
l = i;
while(r < n and s[r-l] == s[r]) r++;
z[i] = r - l;
r --;
}
}
}
return z;
}
class Solution {
public:
int minStartingIndex(string& s, string& pattern) {
string rs = s, rp = pattern;
reverse(begin(rs), end(rs));
reverse(begin(rp), end(rp));
string s1 = pattern + "#" + s;
string s2 = rp + "#" + rs;
vector<int> z = zfunction(s1);
vector<int> rz = zfunction(s2);
int padd = pattern.size() + 1;
for(int i = padd; i < s1.size() - pattern.size() + 1; i++) {
if(z[i] + rz[s2.size() - (i - padd) - pattern.size()] + 1 >= pattern.size()) return i - padd;
}
return -1;
}
};
|
