Table of Contents
Super Functional Strings – 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++ Super Functional Strings HackerRank Solution
#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define LL long long
#define inf INT_MAX/3
#define mod 1000000007ll
#define PI acos(-1.0)
#define linf (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N) FOR(I,0,N)
#define ALL(A) ((A).begin(), (A).end())
#define set0(ar) memset(ar,0,sizeof ar)
#define vsort(v) sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
//cout << fixed << setprecision(20) << p << endl;
template <class T> inline T bigmod(T p,T e,T M){
LL ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
const int N = 3e5+10; // 3* MX size
int A[N] , rnk[N] , sa[N] , height[N];
char str[N];
void ini()
{
memset(A,0,sizeof A);
memset(rnk,0,sizeof rnk);
memset(sa,0,sizeof sa);
memset(height,0,sizeof height);
}
namespace Suffix_array
{
# define F(x) ((x)/3+((x)%3==1?0:tb))
# define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[N * 3] , wb[N * 3] , wv[N * 3] , ws[N * 3];
int c0(int *r, int a, int b)
{
return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2];
}
int c12(int k, int *r, int a, int b)
{
if (k == 2)
return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1);
else return r[a] < r[b] || r[a] == r[b] && wv[a + 1] < wv[b + 1];
}
void sort(int *r, int *a, int *b, int n, int m)
{
int i;
for (i = 0; i < n; i++) wv[i] = r[a[i]];
for (i = 0; i < m; i++) ws[i] = 0;
for (i = 0; i < n; i++) ws[wv[i]]++;
for (i = 1; i < m; i++) ws[i] += ws[i-1];
for (i = n-1; i >= 0; i--) b[--ws[wv[i]]] = a[i];
return;
}
void dc3(int *r, int *sa, int n, int m)
{
int i, j, *rn = r + n;
int *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p;
r[n] = r[n + 1] = 0;
for (i = 0; i < n; i++) if (i % 3 != 0) wa[tbc++] = i;
sort(r + 2, wa, wb, tbc, m);
sort(r + 1, wb, wa, tbc, m);
sort(r, wa, wb, tbc, m);
for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p-1 : p++;
if (p < tbc) dc3(rn, san, tbc, p);
else for (i = 0; i < tbc; i++) san[rn[i]] = i;
for (i = 0; i < tbc; i++) if (san[i] < tb) wb[ta++] = san[i] * 3;
if (n % 3 == 1) wb[ta++] = n-1;
sort(r, wb, wa, ta, m);
for (i = 0; i < tbc; i++) wv[wb[i] = G(san[i])] = i;
for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
for (; i < ta; p++) sa[p] = wa[i++];
for (; j < tbc; p++) sa[p] = wb[j++];
}
void da(int str[],int sa[],int rnk[],int height[],int n,int m)
{
for (int i = n; i < n * 3; i++)
str[i] = 0;
dc3 (str , sa , n + 1 , m);
int i, j, k;
for (i = 0; i < n; i++)
{
sa[i] = sa[i + 1];
rnk[sa[i]] = i;
}
for (i = 0, j = 0, k = 0; i < n; height[rnk[i ++]] = k)
if (rnk[i] > 0)
for (k ? k--: 0 , j = sa[rnk[i]-1];
i + k < n && j + k < n && str[i + k] == str[j + k];
k++);
}
} using namespace Suffix_array;
LL pow_sum[27][100001];
string S;
int pre[100001][27], ar[100001];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
FOR(i, 1, 100001) pow_sum[0][i] = 1;
FOR(i, 1, 27){
FOR(j, 1, 100001){
pow_sum[i][j] = (pow_sum[i-1][j] * (LL)j) % mod;
}
}
REP(i, 27){
FOR(j, 1, 100001) pow_sum[i][j] = (pow_sum[i][j] + pow_sum[i][j-1]) % mod;
}
int T; cin >> T;
while(T--){
cin >> S;
LL res = 0;
REP(i, S.size()) A[i] = S[i];
da(A, sa, rnk, height, S.size(), 128);
ar[sa[0]] = 0;
FOR(i, 1, S.size()){
ar[sa[i]] = height[i];
}
for(int i = S.size()-1; i >= 0; i--){
REP(j, 26){
if(i == S.size()-1)pre[i][j] = S.size();
else pre[i][j] = pre[i+1][j];
}
pre[i][S[i]-'a'] = i;
vector < int > vc;
REP(j, 26){
vc.pb(pre[i][j]);
}
vsort(vc);
REP(j, vc.size()){
if(vc[j] == S.size()) break;
int nxt = S.size();
if(j < vc.size()-1 && vc[j+1] != S.size()) nxt = vc[j+1];
if(nxt-i < ar[i]) continue;
int r = nxt - i;
int l = vc[j] - i + 1;
if(l < ar[i]+1) l = ar[i]+1;
res = (res + pow_sum[j+1][r] - pow_sum[j+1][l-1] + mod) % mod;
}
}
cout << res << endl;
}
}
Java Super Functional Strings HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class D {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int mod = 1000000007;
long[][] psums = new long[27][100005];
long[] tp = new long[100005];
Arrays.fill(tp, 1);
for(int i = 0;i < 27;i++){
psums[i][0] = 1;
for(int j = 1;j < 100005;j++){
psums[i][j] = psums[i][j-1] + tp[j];
if(psums[i][j] >= mod)psums[i][j] -= mod;
tp[j] = tp[j] * j % mod;
}
}
for(int T = ni();T > 0;T--){
char[] s = ns().toCharArray();
int n = s.length;
int[][] nexts = new int[n+1][26];
Arrays.fill(nexts[n], n);
// +1
for(int j = n-1;j >= 0;j--){
for(int k = 0;k < 26;k++){
nexts[j][k] = nexts[j+1][k];
}
nexts[j][s[j]-'a'] = j;
}
int[] sa = sa(s);
int[] lcp = buildLCP(s, sa);
long ret = 0;
for(int i = 0;i < n;i++){
// lcp+1,...,n-sa[i]
Arrays.sort(nexts[sa[i]]);
for(int j = 1;j <= 26;j++){
int ne = j == 26 ? n-sa[i] : nexts[sa[i]][j]-sa[i];
int pr = nexts[sa[i]][j-1]-sa[i]+1;
// [pr,ne)
// tr(j, pr, ne, lcp[i]+1);
pr = Math.max(pr, lcp[i]+1);
if(pr <= ne){
ret += psums[j][ne]-psums[j][pr-1];
}
}
}
ret %= mod;
if(ret < 0)ret += mod;
out.println(ret);
}
}
private static interface BaseArray {
public int get(int i);
public void set(int i, int val);
public int update(int i, int val);
}
private static class CharArray implements BaseArray {
private char[] m_A = null;
private int m_pos = 0;
CharArray(char[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i] & 0xffff;
}
public void set(int i, int val) {
m_A[m_pos + i] = (char) (val & 0xffff);
}
public int update(int i, int val) {
return m_A[m_pos + i] += val & 0xffff;
}
}
private static class IntArray implements BaseArray {
private int[] m_A = null;
private int m_pos = 0;
IntArray(int[] A, int pos) {
m_A = A;
m_pos = pos;
}
public int get(int i) {
return m_A[m_pos + i];
}
public void set(int i, int val) {
m_A[m_pos + i] = val;
}
public int update(int i, int val) {
return m_A[m_pos + i] += val;
}
}
/* find the start or end of each bucket */
private static void getCounts(BaseArray T, BaseArray C, int n, int k) {
int i;
for(i = 0;i < k;++i){
C.set(i, 0);
}
for(i = 0;i < n;++i){
C.update(T.get(i), 1);
}
}
private static void getBuckets(BaseArray C, BaseArray B, int k, boolean end) {
int i, sum = 0;
if(end != false){
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum);
}
}else{
for(i = 0;i < k;++i){
sum += C.get(i);
B.set(i, sum - C.get(i));
}
}
}
/* sort all type LMS suffixes */
private static void LMSsort(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
for(i = 0;i < n;++i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[b++] = (T.get(j) < c1) ? ~j : j;
SA[i] = 0;
}else if(j < 0){
SA[i] = ~j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
--j;
SA[--b] = (T.get(j) > c1) ? ~(j + 1) : j;
SA[i] = 0;
}
}
}
private static int LMSpostproc(BaseArray T, int[] SA, int n, int m) {
int i, j, p, q, plen, qlen, name;
int c0, c1;
boolean diff;
/*
* compact all the sorted substrings into the first m items of SA 2*m
* must be not larger than n (proveable)
*/
for(i = 0;(p = SA[i]) < 0;++i){
SA[i] = ~p;
}
if(i < m){
for(j = i, ++i;;++i){
if((p = SA[i]) < 0){
SA[j++] = ~p;
SA[i] = 0;
if(j == m){
break;
}
}
}
}
/* store the length of all substrings */
i = n - 1;
j = n - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[m + ((i + 1) >> 1)] = j - i;
j = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
/* find the lexicographic names of all substrings */
for(i = 0, name = 0, q = n, qlen = 0;i < m;++i){
p = SA[i];
plen = SA[m + (p >> 1)];
diff = true;
if((plen == qlen) && ((q + plen) < n)){
for(j = 0;(j < plen) && (T.get(p + j) == T.get(q + j));++j){
}
if(j == plen){
diff = false;
}
}
if(diff != false){
++name;
q = p;
qlen = plen;
}
SA[m + (p >> 1)] = name;
}
return name;
}
/* compute SA and BWT */
private static void induceSA(BaseArray T, int[] SA, BaseArray C,
BaseArray B, int n, int k) {
int b, i, j;
int c0, c1;
/* compute SAl */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, false); /* find starts of buckets */
j = n - 1;
b = B.get(c1 = T.get(j));
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
for(i = 0;i < n;++i){
j = SA[i];
SA[i] = ~j;
if(0 < j){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[b++] = ((0 < j) && (T.get(j - 1) < c1)) ? ~j : j;
}
}
/* compute SAs */
if(C == B){
getCounts(T, C, n, k);
}
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = n - 1, b = B.get(c1 = 0);0 <= i;--i){
if(0 < (j = SA[i])){
if((c0 = T.get(--j)) != c1){
B.set(c1, b);
b = B.get(c1 = c0);
}
SA[--b] = ((j == 0) || (T.get(j - 1) > c1)) ? ~j : j;
}else{
SA[i] = ~j;
}
}
}
/*
* find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working space
* (excluding T and SA) of at most 2n+O(1) for a constant alphabet
*/
private static void SA_IS(BaseArray T, int[] SA, int fs, int n, int k) {
BaseArray C, B, RA;
int i, j, b, m, p, q, name, newfs;
int c0, c1;
int flags = 0;
if(k <= 256){
C = new IntArray(new int[k], 0);
if(k <= fs){
B = new IntArray(SA, n + fs - k);
flags = 1;
}else{
B = new IntArray(new int[k], 0);
flags = 3;
}
}else if(k <= fs){
C = new IntArray(SA, n + fs - k);
if(k <= (fs - k)){
B = new IntArray(SA, n + fs - k * 2);
flags = 0;
}else if(k <= 1024){
B = new IntArray(new int[k], 0);
flags = 2;
}else{
B = C;
flags = 8;
}
}else{
C = B = new IntArray(new int[k], 0);
flags = 4 | 8;
}
/*
* stage 1: reduce the problem by at least 1/2 sort all the
* LMS-substrings
*/
getCounts(T, C, n, k);
getBuckets(C, B, k, true); /* find ends of buckets */
for(i = 0;i < n;++i){
SA[i] = 0;
}
b = -1;
i = n - 1;
j = n;
m = 0;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
if(0 <= b){
SA[b] = j;
}
b = B.update(c1, -1);
j = i;
++m;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
if(1 < m){
LMSsort(T, SA, C, B, n, k);
name = LMSpostproc(T, SA, n, m);
}else if(m == 1){
SA[b] = j + 1;
name = 1;
}else{
name = 0;
}
/*
* stage 2: solve the reduced problem recurse if names are not yet
* unique
*/
if(name < m){
if((flags & 4) != 0){
C = null;
B = null;
}
if((flags & 2) != 0){
B = null;
}
newfs = (n + fs) - (m * 2);
if((flags & (1 | 4 | 8)) == 0){
if((k + name) <= newfs){
newfs -= k;
}else{
flags |= 8;
}
}
for(i = m + (n >> 1) - 1, j = m * 2 + newfs - 1;m <= i;--i){
if(SA[i] != 0){
SA[j--] = SA[i] - 1;
}
}
RA = new IntArray(SA, m + newfs);
SA_IS(RA, SA, newfs, m, name);
RA = null;
i = n - 1;
j = m * 2 - 1;
c0 = T.get(n - 1);
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
for(;0 <= i;){
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) <= c1));
if(0 <= i){
SA[j--] = i + 1;
do{
c1 = c0;
}while ((0 <= --i) && ((c0 = T.get(i)) >= c1));
}
}
for(i = 0;i < m;++i){
SA[i] = SA[m + SA[i]];
}
if((flags & 4) != 0){
C = B = new IntArray(new int[k], 0);
}
if((flags & 2) != 0){
B = new IntArray(new int[k], 0);
}
}
/* stage 3: induce the result for the original problem */
if((flags & 8) != 0){
getCounts(T, C, n, k);
}
/* put all left-most S characters into their buckets */
if(1 < m){
getBuckets(C, B, k, true); /* find ends of buckets */
i = m - 1;
j = n;
p = SA[m - 1];
c1 = T.get(p);
do{
q = B.get(c0 = c1);
while (q < j){
SA[--j] = 0;
}
do{
SA[--j] = p;
if(--i < 0){
break;
}
p = SA[i];
}while ((c1 = T.get(p)) == c0);
}while (0 <= i);
while (0 < j){
SA[--j] = 0;
}
}
induceSA(T, SA, C, B, n, k);
C = null;
B = null;
}
/* char */
public static void suffixsort(char[] T, int[] SA, int n) {
if((T == null) || (SA == null) || (T.length < n) || (SA.length < n)){
return;
}
if(n <= 1){
if(n == 1){
SA[0] = 0;
}
return;
}
SA_IS(new CharArray(T, 0), SA, 0, n, 128);
}
public static int[] sa(char[] T)
{
int n = T.length;
int[] sa = new int[n];
suffixsort(T, sa, n);
return sa;
}
public static int[] buildLCP(char[] str, int[] sa)
{
int n = str.length;
int h = 0;
int[] lcp = new int[n];
int[] isa = new int[n];
for(int i = 0;i < n;i++)isa[sa[i]] = i;
for(int i = 0;i < n;i++){
if(isa[i] > 0){
for(int j = sa[isa[i]-1]; j+h<n && i+h<n && str[j+h] == str[i+h]; h++);
lcp[isa[i]] = h;
}else{
lcp[isa[i]] = 0;
}
if(h > 0)h--;
}
return lcp;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new D().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Super Functional Strings HackerRank Solution
from string import ascii_lowercase
from bisect import bisect_left, bisect_right
from itertools import zip_longest, islice
MOD = 7 + 10 ** 9
N = 10 ** 5
sum_pow = [[0] * (N + 1) for k in range(27)]
for k in range(1, 27):
for n in range(1, N + 1):
sum_pow[k][n] = (sum_pow[k][n - 1] + pow(n, k, MOD)) % MOD
def get_sp(left, right, k):
if left > right or right <= 0:
return 0
if left <= 0:
return sum_pow[k][right]
return (sum_pow[k][right] + MOD - sum_pow[k][left - 1]) % MOD
def all_occ(s):
n = len(s)
occ = [[] for _ in range(26)]
for i in range(n):
occ[ord(s[i]) - ord('a')].append(i)
return occ
def occ_from_i(occ, i):
occ_i = []
for j in range(26):
if len(occ[j]) == 0 or i > occ[j][-1]:
continue
first = bisect_left(occ[j], i)
occ_i.append(occ[j][first])
return sorted(occ_i)
def sorted_idx(items):
unique = sorted(set(items))
idx = dict(zip(unique, range(len(unique))))
return [idx[v] for v in items]
def suffix_array(s):
n = len(s)
k = 1
sa = sorted_idx(s)
while max(sa) < n - 1:
sa = sorted_idx([a * (n + 1) + b + 1 for
(a, b) in zip_longest(sa,
islice(sa, k, None),
fillvalue=-1)])
k <<= 1
return sa
def lcp_sa(s):
inv_sa = suffix_array(s)
n = len(inv_sa)
sa = [0] * n
for i in range(n):
sa[inv_sa[i]] = i
lcp = [0] * n
k = 0
for i in range(n):
if inv_sa[i] == n - 1:
k = 0
continue
j = sa[inv_sa[i]+1]
while i + k < n and j + k < n and s[i + k] == s[j + k]:
k += 1
lcp[inv_sa[i] + 1] = k
if k > 0:
k -= 1
return sa, lcp
def solve(s):
n = len(s)
occ = all_occ(s)
sa, lcp = lcp_sa(s)
ans = 0
#print(sa)
#print(lcp)
for i in range(n):
o = occ_from_i(occ, sa[i])
t = sa[i] + lcp[i]
if t >= o[-1]:
ans = (ans + get_sp(lcp[i] + 1, n - sa[i], len(o))) % MOD
continue
k = bisect_right(o, t)
ans = (ans + get_sp(lcp[i] + 1, o[k] - sa[i], k)) % MOD
for j in range(k + 1, len(o)):
ans = (ans + get_sp(o[j - 1] - sa[i] + 1, o[j] - sa[i], j)) % MOD
ans = (ans + get_sp(o[-1] - sa[i] + 1, n - sa[i], len(o))) % MOD
return ans
def sum_p_bf(left, right, k):
ans = 0
for n in range(max(left, 1), right + 1):
ans = (ans + pow(n, k, MOD)) % MOD
return ans
q = int(input().strip())
for _ in range(q):
string = input().strip()
print(solve(string))
Python 2 Super Functional Strings HackerRank Solution
#!/bin/python
from __future__ import print_function
import os
import sys
#
# Complete the superFunctionalStrings function below.
#
def kasai(txt, sa):
n = len(sa)
lcp = [0 for _ in range(n)]
inv = [0 for _ in range(n)]
for i in range(n):
inv[sa[i]] = i
k = 0
for i in range(n):
if inv[i] == n - 1:
k = 0
continue
j = sa[inv[i]+1]
while i+k<n and j+k<n and txt[i+k]==txt[j+k]:
k += 1
lcp[inv[i]] = k
if k>0:
k -= 1
return lcp
def distinct_substr_chars(s, begin, end, dist_map):
for i in range(begin, end+1):
c = ord(s[i]) - ord('a')
dist_map[c]+=1
def dist_map_clear(dist_map):
for i in range(26):
dist_map[i] = 0;
def dist_map_size(dist_map):
count = 0;
for i in range(26):
if (dist_map[i] > 0):
count+=1
return count
def superFunctionalStrings(s):
n = len(s)
sa = [t[1] for t in sorted((s[i:],i) for i in range(len(s)))]
#print(sa)
lcp = kasai(s, sa)
#print(lcp)
count = 0
mod = 1000000007
for i in range(len(s)):
if (i == 0):
suffix_len = 1;
else:
suffix_len = lcp[i-1] + 1;
begin_suffix = sa[i]
end = n - begin_suffix
suffix_end = begin_suffix + suffix_len - 1
#print(begin_suffix, s[begin_suffix:suffix_end+1])
#ptr = s[begin_suffix]
dist_map = [0]*26
# distinct_map_clear();
# distinct_chars = distinct_substr_chars(ptr, suffix_len);
distinct_substr_chars(s, begin_suffix, suffix_end, dist_map)
distinct_chars = dist_map_size(dist_map)
count += power[distinct_chars][suffix_len]
#ptr = &str[suffix_end];
ptr = suffix_len+1
for j in range(suffix_end+1, n):
if dist_map[ord(s[j]) - ord('a')] == 0:
dist_map[ord(s[j]) - ord('a')] = 1
distinct_chars += 1
count += power[distinct_chars][ptr] #update_count(j, distinct_chars);
ptr += 1
#update_distinct_chars(ptr, distinct_chars);
count %= mod;
return count
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(raw_input())
modulo = 1000000007
power=[[pow(j,i,modulo) for j in range(100000)] for i in range(27)]
for t_itr in xrange(t):
s = raw_input()
result = superFunctionalStrings(s)
fptr.write(str(result) + '\n')
fptr.close()
C Super Functional Strings HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
#define MOD 1000000007
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
void print(st_node *root,int len);
void suffix_tree(st_node *root,char *str,int len);
long long modPow(long long a,int x);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
char str[100001];
int dp[100000][26];
long long ans,pows[26][100001];
int main(){
int T,len,i,j;
st_node root;
for(i=0;i<26;i++)
for(j=1;j<=100000;j++)
pows[i][j]=(pows[i][j-1]+modPow(j,i+1))%MOD;
scanf("%d",&T);
while(T--){
scanf("%s",str);
len=strlen(str);
for(i=0;i<26;i++)
dp[len-1][i]=-1;
dp[len-1][str[len-1]-MIN_C]=len-1;
for(i=len-2;i>=0;i--){
memcpy(&dp[i][0],&dp[i+1][0],26*sizeof(int));
dp[i][str[i]-MIN_C]=i;
}
suffix_tree(&root,str,len);
ans=0;
print(&root,0);
printf("%lld\n",ans);
}
return 0;
}
void print(st_node *root,int len){
int i,j,idx,from,to,s,dc,last,t,a[26];
if(!root)
return;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
idx=root->edges[i]->suffix_index;
from=idx+len;
to=idx+len+root->edges[i]->to-root->edges[i]->from;
s=dc=0;
last=idx+len-1;
for(j=0;j<26;j++)
if(dp[idx][j]!=-1 && dp[idx][j]<from)
dc++;
else if(dp[idx][j]>=from && dp[idx][j]<=to)
a[s++]=dp[idx][j];
sort_a(a,s);
for(j=0;j<s;j++,dc++){
t=a[j]-1;
if(dc)
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
last=t;
}
t=to;
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
print(root->edges[i]->node,len+root->edges[i]->to-root->edges[i]->from+1);
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<=len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[a_edge]->from+a_len]==str[i])
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}
long long modPow(long long a,int x){
long long res = 1;
while(x>0){
if(x%2)
res=(res*a)%MOD;
a=(a*a)%MOD;
x>>=1;
}
return res;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
