class Solution {
public:
vector<int> getNext(string pattern) {
int len = (int)pattern.length();
vector<int> res(len+1,0);
int j = 0;
for (int i = 1 ; i < len ; i++) {
while (j && pattern[i] != pattern[j]) j = res[j];
if (pattern[i] == pattern[j]) j++;
res[i+1] = j;
}
return res;
}
int searchPosition(string text, string pattern, vector<int>& next) {
int j = 0 , lt = (int)text.length() , lp = (int)pattern.length();
for (int i = 0 ; i < lt ; i++) {
while (j && text[i] != pattern[j]) j = next[j];
if (text[i] == pattern[j]) j++;
if (j == lp) return i-j+1;
}
return -1;
}
bool isSubstr(string pattern, string text, unordered_map<string, vector<int>>& nextmp) {
if (searchPosition(text, pattern, nextmp[pattern]) >= 0) return true;
else return false;
}
vector<string> stringMatching(vector<string>& words) {
sort(words.begin(), words.end(), [](const string& a, const string& b) {
return a.length() < b.length();
});
unordered_map<string, vector<int>> nextmp;
for (auto str : words) {
nextmp[str] = getNext(str);
}
int n = words.size();
vector<string> ans;
unordered_map<string, bool> vis;
for (int i = 0 ; i < n ; i++) {
for (int j = i+1 ; j < n ; j++) {
if (!vis[words[i]] && isSubstr(words[i], words[j], nextmp)) {
ans.push_back(words[i]);
vis[words[i]] = true;
}
}
}
return ans;
}
};
class Solution {
public:
vector<int> processQueries(vector<int>& queries, int m) {
vector<int> p = vector<int>(m, 0);
for (int i = 0 ; i < m ; i++) {
p[i] = i + 1;
}
vector<int> ans;
for (auto q : queries) {
for (int i = 0 ; i < m ; i++) {
if (q == p[i]) {
ans.push_back(i);
for (int j = i ; j >= 1 ; j--) {
p[j] = p[j-1];
}
p[0] = q;
}
}
}
return ans;
}
};
class Solution {
public:
string entityParser(string text) {
int len = text.length();
string ans = "";
for (int i = 0 ; i < len ; ) {
if (text[i] == '&') {
if (text[i+1] == 'q' && text[i+2] == 'u' && text[i+3] == 'o' && text[i+4] == 't' && text[i+5] == ';') {
ans += '"';
i += 6;
} else if (text[i+1] == 'a' && text[i+2] == 'p' && text[i+3] == 'o' && text[i+4] == 's' && text[i+5] == ';') {
ans += '\'';
i += 6;
} else if (text[i+1] == 'a' && text[i+2] == 'm' && text[i+3] == 'p' && text[i+4] == ';') {
ans += '&';
i += 5;
} else if (text[i+1] == 'g' && text[i+2] == 't' && text[i+3] == ';') {
ans += '>';
i += 4;
} else if (text[i+1] == 'l' && text[i+2] == 't' && text[i+3] == ';') {
ans += '<';
i += 4;
} else if (text[i+1] == 'f' && text[i+2] == 'r' && text[i+3] == 'a' && text[i+4] == 's' && text[i+5] == 'l' && text[i+6] == ';') {
ans += '/';
i += 7;
} else {
ans += '&';
i++;
}
} else {
ans += text[i];
i++;
}
}
return ans;
}
};
class Solution {
public:
int numOfWays(int n) {
long long mod = 1000000007;
vector<long long> dp1 = vector<long long>(n, (long long)1);
vector<long long> dp2 = vector<long long>(n, (long long)1);
for (int i = 1 ; i < n ; i++) {
dp1[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)2) % mod;
dp2[i] = (dp1[i-1] * (long long)2 + dp2[i-1] * (long long)3) % mod;
}
long long ans = (long long)6 * (dp1[n-1] + dp2[n-1]) % mod;
return (int)ans;
}
};