We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
using namespace std;
long long stringSimilarity(const string& s) {
int n = s.length();
vector z(n, 0);
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += z[i];
}
return sum;
}
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << stringSimilarity(s) << endl;
}
return 0;
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
String Similarity
You are viewing a single comment's thread. Return to all comments →
using namespace std; long long stringSimilarity(const string& s) { int n = s.length(); vector z(n, 0); z[0] = n; int l = 0, r = 0;
}
int main() { int t; cin >> t; while (t--) { string s; cin >> s; cout << stringSimilarity(s) << endl; } return 0; }