String Similarity- HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ String Similarity HackerRank Solution
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <sstream>
#include <map>
#include <set>
#include <numeric>
#include <memory.h>
#include <cstdio>
#include <assert.h>
#include <numeric>
using namespace std;
#define pb push_back
#define INF 1011111111
#define FOR(i,a,b) for (int _n(b), i(a); i < _n; i++)
#define rep(i,n) FOR(i,0,n)
#define ford(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define CL(a,v) memset((a),(v),sizeof(a))
#define mp make_pair
#define X first
#define Y second
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
vector<ll> z_func(const string &s)
{
int n = s.size();
vector<ll> z(n,0);
int l = 0,r = 0;
FOR(i,1,n)
{
if(i <= r)
z[i] = min(z[i-l], (ll)r-i+1);
while(i+z[i] < n && s[i+z[i]] == s[z[i]]) z[i] ++;
if(i+z[i]-1 > r)
r = i+z[i]-1, l = i;
}
return z;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
int T;
cin >> T;
while(T--)
{
string s;
cin >> s;
vector<ll> z = z_func(s);
cout << 1LL*s.size() + accumulate(all(z), 0LL) << endl;
}
return 0;
}
Java String Similarity HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private void solution() throws IOException {
int ts = in.nextInt();
while (ts-- > 0) {
String s = in.next();
int[] z = zFunc(s);
// System.err.println(Arrays.toString(z));
long res = 0;
for (int x : z) {
res += x;
}
out.println(res + s.length());
}
}
private int[] zFunc(String s) {
int[] res = new int[s.length()];
int left = 0;
int right = 0;
for (int i = 1; i < s.length(); ++i) {
if (i <= right) {
res[i] = Math.min(right - i + 1, res[i - left]);
}
while (i + res[i] < s.length() && s.charAt(res[i]) == s.charAt(i + res[i])) {
++res[i];
}
if (i + res[i] - 1 > right) {
left = i;
right = i + res[i] - 1;
}
}
return res;
}
public void run() {
try {
solution();
in.reader.close();
out.close();
} catch (Exception e) {
e.printStackTrace();
System.exit(1);
}
}
private class Scanner {
StringTokenizer tokenizer;
BufferedReader reader;
public Scanner(Reader reader) {
this.reader = new BufferedReader(reader);
this.tokenizer = new StringTokenizer("");
}
public boolean hasNext() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = reader.readLine();
if (line == null) {
return false;
}
tokenizer = new StringTokenizer(line);
}
return true;
}
public String next() throws IOException {
hasNext();
return tokenizer.nextToken();
}
// public String nextLine() throws IOException {
// tokenizer = new StringTokenizer("");
// return reader.readLine();
// }
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
// public long nextLong() throws IOException {
// return Long.parseLong(next());
// }
}
public static void main(String[] args) throws IOException {
new Solution().run();
}
Scanner in = new Scanner(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}
Python 3 String Similarity HackerRank Solution
#!/usr/bin/py
# Head ends here
def stringSimilarity(string):
n = len(string)
z = [0] * n
zbox_left, zbox_right, z[0] = 0, 0, n
for i in range(1, n):
if i < zbox_right:
k = i - zbox_left
if z[k] < zbox_right - i:
z[i] = z[k]
continue
zbox_left = i
else:
zbox_left = zbox_right = i
while zbox_right < n and string[zbox_right - zbox_left] == string[zbox_right]:
zbox_right += 1
z[i] = zbox_right - zbox_left
return sum(z)
# Tail starts here
if __name__ == '__main__':
t = int(input())
for i in range(0,t):
a=input()
print(stringSimilarity(a))
Python 2 String Similarity HackerRank Solution
def solve():
n = len(W)
sim = [0]*n
sim[0] = n
pos = 1
l = 0
while True:
if pos+l<n and W[pos+l]==W[l]:
l += 1
else:
if pos>=n:
break
if l==0:
pos += 1
continue
sim[pos] = l
flag = l
i = 1
while i<l:
if W[pos+i]==W[0]:
if sim[i]!=l-i:
sim[pos+i] = min(l-i,sim[i])
else:
flag = i
break
i += 1
pos += flag
l -= flag
print sum(sim)
# main
T = int(raw_input())
for i in range(T):
W = raw_input()
solve()
C String Similarity HackerRank Solution
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int64_t int64;
#define MAXN 131072
char data[MAXN]; /* input */
int suf[MAXN]; /* suffix array */
int inv[MAXN]; /* inverse suffix array used during construction. */
int bounds[MAXN]; /* scratch space for updategroups. */
int nbounds; /* len(bounds) */
int n; /* strlen(data) */
int h; /* sort level during construction. */
/* bucketsort sorts data by the first byte, into suf. */
void bucketsort() {
int count[256] = {0};
int i, sum, x;
for (i = 0; i < n; i++)
count[data[i]]++;
/* make count[x] = index of first occurence of x */
sum = 0;
for (i = 0; i < 256; i++) {
x = count[i];
count[i] = sum;
sum += x;
}
for (i = 0; i < n; i++)
suf[count[data[i]]++] = i;
}
/* initgroups: ... */
void initgroups() {
int i, prev;
char ch, group;
/* label continuous same-letter groups with the same group number. */
prev = n-1;
group = data[suf[prev]];
for (i = n-1; i >= 0; i--) {
ch = data[suf[i]];
if (ch < group) {
if (prev == i+1)
suf[i+1] = -1;
group = ch;
prev = i;
}
inv[suf[i]] = prev;
if (prev == 0)
suf[0] = -1;
}
}
int cmp(const void *A, const void *B) {
int sufi, sufj;
sufi = *((int *)A);
sufj = *((int *)B);
if (inv[sufi + h] < inv[sufj + h])
return -1;
if (inv[sufi + h] > inv[sufj + h])
return 1;
return 0;
}
/* updategroups: ... */
void updategroups(int lo, int hi) {
int i, j, g, group, prev;
nbounds = 0;
group = inv[suf[lo] + h];
for (i = lo+1; i < hi; i++) {
g = inv[suf[i] + h];
if (g > group) {
bounds[nbounds++] = i;
group = g;
}
}
bounds[nbounds++] = hi;
prev = lo;
for (i = 0; i < nbounds; i++) {
for (j = prev; j < bounds[i]; j++)
inv[suf[j]] = bounds[i]-1;
if (bounds[i] - prev == 1)
suf[prev] = -1;
prev = bounds[i];
}
}
/* suffixsort computes the suffix array for data. */
void suffixsort() {
int i, pi, pk, s, sl;
bucketsort();
initgroups();
h = 1; /* the index starts 1-sorted */
while (suf[0] > -n) { /* while not single sorted group */
pi = 0; /* pi is first position of group */
sl = 0; /* sl is negated length of sorted groups */
while (pi < n) {
s = suf[pi];
if (s < 0) { /* pi starts a sorted group */
pi -= s;
sl += s;
} else { /* pi starts an unsorted group */
if (sl != 0) {
suf[pi + sl] = sl; /* combine sorted groups before pi */
sl = 0;
}
pk = inv[s] + 1; /* pk-1 is last position of unsorted group */
// sortsplit(pi, pk);
qsort(suf+pi, pk-pi, sizeof suf[0], cmp);
updategroups(pi, pk);
pi = pk; /* next group */
}
}
if (sl != 0) { /* if the array ends with a sorted group */
suf[pi + sl] = sl; /* combine sorted groups at end */
}
h *= 2;
}
/* reconstruct suffix array from inverse */
for (i = 0; i < n; i++)
suf[inv[i]] = i;
}
/* similarity computes the sum of all suffix matches to data. */
int64 similarity() {
int a, b, i, j, k, mid;
int64 sum;
a = 0;
b = n;
sum = 0;
for (k = 0; data[k] != '$'; k++) {
/* find the first index where data[0..k] would be the prefix */
i = a;
j = b;
while (i < j) {
mid = (i + j) / 2;
if (data[suf[mid] + k] < data[k])
i = mid + 1;
else
j = mid;
}
a = i;
/* starting at a, find the first index at which data[0..k] is not the prefix */
i = a;
j = b;
while (i < j) {
mid = (i + j) / 2;
if (data[suf[mid] + k] <= data[k])
i = mid + 1;
else
j = mid;
}
b = i;
sum += (b - a);
}
return sum;
}
int64 naive() {
int64 sum;
int i, j, k;
sum = 0;
for (i = 0; i < n-1; i++) {
for (j = i, k = 0; j < n-1; j++, k++)
if (data[j] == data[k])
sum++;
else
break;
}
return sum;
}
int main() {
int ncases;
char buf[100];
fgets(buf, sizeof buf, stdin);
ncases = atoi(buf);
while (ncases-- > 0) {
fgets(data, sizeof data, stdin);
n = strlen(data);
if (n > 0 && data[n-1] == '\n')
data[--n] = '\0';
assert(n <= 100000);
if (n == 0) {
printf("0\n");
continue;
}
if (n == 1) {
printf("1\n");
continue;
}
data[n++] = '$';
data[n] = '\0';
suffixsort();
printf("%lld\n", similarity());
}
return 0;
}