# Cherry and Pyramid Solutions CENS20C

Page Contents

## Cherry and Pyramid Solutions

Cherry has a string S comprising of lowercase English letters. Utilizing this string, he framed a pyramid of boundless length with specific guidelines:

N-th line of pyramid contains N characters.

Each line of pyramid starts with the main character of the string.

The resulting characters of the line are added to the string in cyclic style, until the size of string for that Row is reached (See model pyramid for better understanding).

He has another string T of littler (or equivalent) size.

You are asked Q inquiries. Each question is furnished with a column number N. The response to the inquiry is number of events of string T in that specific column of pyramid. No of events of String T in a string V would imply that you’d have to discover number of substrings Vi,Vi+1…Vj which are equivalent to String T, where i≤j.

For eg: If the string is code, at that point the pyramid will be of the structure:

co

cod

code

codec

codeco

codecod

codecode

codecodec

codecodeco

Information:

The principal line contains string S — comprising of lowercase English letters.

The subsequent line contains string T — comprising of lowercase English letters.

Next line contains a number Q — the quantity of questions.

At that point follow Q lines with questions depictions. Every one of them contains a solitary whole number N indicating the column number of pyramid.

Yield: Print Q lines. The I-th of them ought to contain a whole number signifying events of string T in that specific line.

Imperatives

1≤|S|≤105

1≤|T|≤|S|

1≤Q≤105

1≤N≤109

Test Input:

codechef

chefcode

12

1455

Test Output:

181

Clarification:

Pyramid will be shaped as clarified in the announcement.

Question 1: Row number 4 of the pyramid is code. The quantity of events of chefcode in code is 0.

Question 2: Row number 12 of the pyramid is codechefcode. The quantity of events of chefcode in codechefcode is 1.

Solution

import java.util.*;

import java.io.*;

import java.awt.*;

import java.math.*;

public class Main implements Runnable {

@Override

public void run() {

try {

new Solver().solve();

System.exit(0);

} catch (Exception | Error e) {

e.printStackTrace();

System.exit(1);

}

}

public static void main(String[] args) throws Exception {

//new Thread(null, new Main(), “Solver”, 1l << 25).start();

new Main().run();

}

}

class Solver {

final Helper hp;

final int MAXN = 1000_006;

final long MOD = (long) 1e9 + 7;

final Timer timer;

Solver() {

hp = new Helper(MOD, MAXN);

hp.initIO(System.in, System.out);

timer = new Timer();

@Override

public void run() {

try {

hp.flush();

System.exit(0);

} catch (Exception e) {

}

}

};

}

void solve() throws Exception {

int tc = TESTCASES ? hp.nextInt() : 1;

for (int tce = 1; tce <= tc; ++tce) solve(tce);

timer.cancel();

hp.flush();

}

boolean TESTCASES = false;

void solve(int tc) throws Exception {

int i, j, k;

final long PRIME = 97, MOD = 777767777;

String S = hp.next(), T = hp.next();

int N = S.length(), M = T.length();

RabinKarp rkS = new RabinKarp((S + S).toCharArray(), PRIME, MOD);

RabinKarp rkT = new RabinKarp(T.toCharArray(), PRIME, MOD);

ArrayList<Integer> endIdx = new ArrayList<>();

for (i = 0; i < N; ++i) {

int start = i, end = i + M – 1;

if (rkS.getHash(start, end) == rkT.getHash(0, M – 1)) {

}

}

System.err.println(endIdx);

int Q = hp.nextInt();

while (Q– > 0) {

long row = hp.nextLong();

long ans = 0;

/*for (int end : endIdx) if (end < row) {

ans += (row – end – 1) / N + 1;

}*/

for (i = 0; i < endIdx.size(); ++i) if (endIdx.get(i) < row) {

long val = (row – endIdx.get(i) – 1) / N;

j = binSearch(i, endIdx.size() – 1, row, val, N, endIdx);

ans += (val + 1) * (j – i + 1);

i = j;

}

hp.println(ans);

}

}

int binSearch(int l, int r, long row, long val, int N, ArrayList<Integer> ar) {

while (true) {

int mid = l + r >> 1;

if (l == mid) {

if (ar.get(r) < row && (row – ar.get(r) – 1) / N >= val) return r;

else if (ar.get(l) < row && (row – ar.get(l) – 1) / N >= val) return l;

else return 7 / 0;

} else if (ar.get(mid) < row && (row – ar.get(mid) – 1) / N >= val) {

l = mid;

} else {

r = mid – 1;

}

}

}

}

class RabinKarp {

final long PRIME, MOD;

int N;

long[] hash, pow, inv;

public RabinKarp(char[] S, long P, long M) { // M must be a prime number

PRIME = P;

MOD = M;

N = S.length;

int i;

pow = new long[Math.max(2, N)];

pow[0] = 1;

pow[1] = PRIME;

for (i = 2; i < pow.length; ++i) pow[i] = pow[i – 1] * pow[1] % MOD;

inv = new long[Math.max(2, N)];

inv[0] = 1;

inv[1] = pow(PRIME, MOD – 2, MOD);

for (i = 2; i < inv.length; ++i) inv[i] = inv[i – 1] * inv[1] % MOD;

hash = new long[N];

for (i = 0; i < N; ++i) {

hash[i] = hashFunc(S[i], i);

if (i > 0) {

hash[i] += hash[i – 1];

if (hash[i] >= MOD) hash[i] -= MOD;

}

}

}

public long getHash(int l, int r) {

long h = hash[r];

if (l > 0) {

h -= hash[l – 1];

if (h < 0) h += MOD;

}

h = shiftHash(h, l, 0);

return h;

}

public int size() {

return N;

}

private long hashFunc(char ch, int idx) {

return shiftHash(ch, 0, idx);

}

public long shiftHash(long initialHash, int fromIndex, int toIndex) {

if (fromIndex < toIndex) {

return initialHash * pow[toIndex – fromIndex] % MOD;

} else if (fromIndex > toIndex) {

return initialHash * inv[fromIndex – toIndex] % MOD;

} else {

return initialHash;

}

}

private long pow(long base, long exp, long MOD) {

base %= MOD;

long ret = 1;

while (exp > 0) {

if ((exp & 1) == 1) ret = ret * base % MOD;

base = base * base % MOD;

exp >>= 1;

}

return ret;

}

}

class Helper {

final long MOD;

final int MAXN;

final Random rnd;

public Helper(long mod, int maxn) {

MOD = mod;

MAXN = maxn;

rnd = new Random();

public static int[] sieve;

public static ArrayList<Integer> primes;

public void setSieve() {

primes = new ArrayList<>();

sieve = new int[MAXN];

int i, j;

for (i = 2; i < MAXN; ++i)

if (sieve[i] == 0) {

for (j = i; j < MAXN; j += i) {

sieve[j] = i;

}

}

}

public static long[] factorial;

public void setFactorial() {

factorial = new long[MAXN];

factorial[0] = 1;

for (int i = 1; i < MAXN; ++i) factorial[i] = factorial[i – 1] * i % MOD;

}

public long getFactorial(int n) {

if (factorial == null) setFactorial();

return factorial[n];

}

public long ncr(int n, int r) {

if (r > n) return 0;

if (factorial == null) setFactorial();

long numerator = factorial[n];

long denominator = factorial[r] * factorial[n – r] % MOD;

return numerator * pow(denominator, MOD – 2, MOD) % MOD;

}

public long[] getLongArray(int size) throws Exception {

long[] ar = new long[size];

for (int i = 0; i < size; ++i) ar[i] = nextLong();

return ar;

}

public int[] getIntArray(int size) throws Exception {

int[] ar = new int[size];

for (int i = 0; i < size; ++i) ar[i] = nextInt();

return ar;

}

public String[] getStringArray(int size) throws Exception {

String[] ar = new String[size];

for (int i = 0; i < size; ++i) ar[i] = next();

return ar;

}

public String joinElements(long… ar) {

StringBuilder sb = new StringBuilder();

for (long itr : ar) sb.append(itr).append(” “);

return sb.toString().trim();

}

public String joinElements(int… ar) {

StringBuilder sb = new StringBuilder();

for (int itr : ar) sb.append(itr).append(” “);

return sb.toString().trim();

}

public String joinElements(String… ar) {

StringBuilder sb = new StringBuilder();

for (String itr : ar) sb.append(itr).append(” “);

return sb.toString().trim();

}

public String joinElements(Object… ar) {

StringBuilder sb = new StringBuilder();

for (Object itr : ar) sb.append(itr).append(” “);

return sb.toString().trim();

}

public long gcd(long a, long b) {

return b == 0 ? a : gcd(b, a % b);

}

public int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a % b);

}

public long max(long… ar) {

long ret = ar[0];

for (long itr : ar) ret = Math.max(ret, itr);

return ret;

}

public int max(int… ar) {

int ret = ar[0];

for (int itr : ar) ret = Math.max(ret, itr);

return ret;

}

public long min(long… ar) {

long ret = ar[0];

for (long itr : ar) ret = Math.min(ret, itr);

return ret;

}

public int min(int… ar) {

int ret = ar[0];

for (int itr : ar) ret = Math.min(ret, itr);

return ret;

}

public long sum(long… ar) {

long sum = 0;

for (long itr : ar) sum += itr;

return sum;

}

public long sum(int… ar) {

long sum = 0;

for (int itr : ar) sum += itr;

return sum;

}

public void shuffle(int[] ar) {

int r;

for (int i = 0; i < ar.length; ++i) {

r = rnd.nextInt(ar.length);

if (r != i) {

ar[i] ^= ar[r];

ar[r] ^= ar[i];

ar[i] ^= ar[r];

}

}

}

public void shuffle(long[] ar) {

int r;

for (int i = 0; i < ar.length; ++i) {

r = rnd.nextInt(ar.length);

if (r != i) {

ar[i] ^= ar[r];

ar[r] ^= ar[i];

ar[i] ^= ar[r];

}

}

}

public void reverse(int[] ar) {

int r;

for (int i = 0; i < ar.length; ++i) {

r = ar.length – 1 – i;

if (r > i) {

ar[i] ^= ar[r];

ar[r] ^= ar[i];

ar[i] ^= ar[r];

}

}

}

public void reverse(long[] ar) {

int r;

for (int i = 0; i < ar.length; ++i) {

r = ar.length – 1 – i;

if (r > i) {

ar[i] ^= ar[r];

ar[r] ^= ar[i];

ar[i] ^= ar[r];

}

}

}

public long pow(long base, long exp, long MOD) {

base %= MOD;

long ret = 1;

while (exp > 0) {

if ((exp & 1) == 1) ret = ret * base % MOD;

base = base * base % MOD;

exp >>= 1;

}

return ret;

}

static final int BUFSIZE = 1 << 20;

static byte[] buf;

static int index, total;

static InputStream in;

static BufferedWriter bw;

public void initIO(InputStream is, OutputStream os) {

try {

in = is;

bw = new BufferedWriter(new OutputStreamWriter(os));

buf = new byte[BUFSIZE];

} catch (Exception e) {

}

}

public void initIO(String inputFile, String outputFile) {

try {

in = new FileInputStream(inputFile);

bw = new BufferedWriter(new OutputStreamWriter(

new FileOutputStream(outputFile)));

buf = new byte[BUFSIZE];

} catch (Exception e) {

}

}

private int scan() throws Exception {

if (index >= total) {

index = 0;

if (total <= 0)

return -1;

}

return buf[index++];

}

public String next() throws Exception {

int c;

for (c = scan(); c <= 32; c = scan()) ;

StringBuilder sb = new StringBuilder();

for (; c > 32; c = scan())

sb.append((char) c);

return sb.toString();

}

public int nextInt() throws Exception {

int c, val = 0;

for (c = scan(); c <= 32; c = scan()) ;

boolean neg = c == ‘-‘;

if (c == ‘-‘ || c == ‘+’)

c = scan();

for (; c >= ‘0’ && c <= ‘9’; c = scan())

val = (val << 3) + (val << 1) + (c & 15);

return neg ? -val : val;

}

public long nextLong() throws Exception {

int c;

long val = 0;

for (c = scan(); c <= 32; c = scan()) ;

boolean neg = c == ‘-‘;

if (c == ‘-‘ || c == ‘+’)

c = scan();

for (; c >= ‘0’ && c <= ‘9’; c = scan())

val = (val << 3) + (val << 1) + (c & 15);

return neg ? -val : val;

}

public void print(Object a) throws Exception {

bw.write(a.toString());

}

public void printsp(Object a) throws Exception {

print(a);

print(” “);

}

public void println() throws Exception {

bw.write(“n”);

}

public void println(Object a) throws Exception {

print(a);

println();

}

public void flush() throws Exception {

bw.flush();

}

}