# Build a String

### Problem Statement :

```Greg wants to build a string, S of length N. Starting with an empty string, he can perform 2 operations:

1. Add a character to the end of S for A dollars.
2. Copy any substring of S, and then add it to the end of S for B dollars.

Calculate minimum amount of money Greg needs to build S.

Input Format

The first line contains number of testcases T.

The 2 x T  subsequent lines each describe a test case over 2 lines:
The first contains 3 space-separated integers, , N , A and B, respectively.
The second contains  S (the string Greg wishes to build).

Constraints

1   <=   T  <=   3
1   <=   N  <=   3 x 10^4
1  <=   A,  B  <=  10000

S is composed of lowercase letters only.

Output Format

On a single line for each test case, print the minimum cost (as an integer) to build S.```

### Solution :

```                            ```Solution in C :

In  C++  :

#include <cstdio>
#include <algorithm>

using namespace std;

const int inf=1000000000;
struct suffix
{
int s1,s2,poz;
bool operator <(const suffix &aux) const
{
if(s1==aux.s1) return s2<aux.s2;
else return s1<aux.s1;
}
bool operator ==(const suffix &aux) const
{
return s1==aux.s1 && s2==aux.s2;
}
}s[30010];
struct arbint
{
int minn,lazy;
}arb[200010];
int p[17][30010],logg[30010],pas[30010];
int poz[30010],st[30010],dr[30010],rmq[17][30010],n,sol;
char sir[30010];

int LCP(int x,int y)
{
int rez=0;
for(int i=logg[n];i>=0 && x<=n && y<=n;i--)
if(p[i][x]==p[i][y]) {rez+=1<<i;x+=1<<i;y+=1<<i;}
return rez;
}

void arbint_init(int nod,int st,int dr)
{
arb[nod].minn=arb[nod].lazy=inf;
if(st==dr) return;
int mid=(st+dr)/2;
arbint_init(nod*2,st,mid);
arbint_init(nod*2+1,mid+1,dr);
}

void update(int nod,int st,int dr)
{
arb[nod].minn=min(arb[nod].minn,arb[nod].lazy);
if(st<dr)
{
arb[nod*2].lazy=min(arb[nod*2].lazy,arb[nod].lazy);
arb[nod*2+1].lazy=min(arb[nod*2+1].lazy,arb[nod].lazy);
}
}

void arbint_update(int nod,int st,int dr,int left,int right,int val)
{
if(left<=st && dr<=right)
{
arb[nod].lazy=min(arb[nod].lazy,val);
update(nod,st,dr);
return;
}
update(nod,st,dr);
int mid=(st+dr)/2;
if(left<=mid) arbint_update(nod*2,st,mid,left,right,val);
else update(nod*2,st,mid);
if(mid<right) arbint_update(nod*2+1,mid+1,dr,left,right,val);
else update(nod*2+1,mid+1,dr);
arb[nod].minn=min(arb[nod*2].minn,arb[nod*2+1].minn);
}

void arbint_query(int nod,int st,int dr,int poz)
{
update(nod,st,dr);
if(st==dr)
{
sol=arb[nod].minn;
return;
}
int mid=(st+dr)/2;
if(poz<=mid) arbint_query(nod*2,st,mid,poz);
else arbint_query(nod*2+1,mid+1,dr,poz);
}

int get_min(int x,int y)
{
int lim=logg[y-x+1];
return min(rmq[lim][x],rmq[lim][y-(1<<lim)+1]);
}

int main()
{
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
int t;
for(scanf("%d",&t);t;t--)
{
int cost1,cost2;
scanf("%d%d%d\n%s",&n,&cost1,&cost2,sir+1);
for(int i=2;i<=n;i++) logg[i]=logg[i/2]+1;
for(int i=1;i<=n;i++)
{
p[0][i]=sir[i];
s[i].poz=i;
}
for(int i=1;i<=logg[n]+1;i++)
{
for(int j=1;j<=n;j++)
{
s[j].s1=p[i-1][s[j].poz];
if(s[j].poz+(1<<(i-1))<=n) s[j].s2=p[i-1][s[j].poz+(1<<(i-1))];
else s[j].s2=-1;
}
sort(s+1,s+n+1);
for(int j=1;j<=n;j++)
if(j>1 && s[j]==s[j-1]) p[i][s[j].poz]=p[i][s[j-1].poz];
else p[i][s[j].poz]=j;
}
for(int i=1;i<=n;i++) rmq[0][i]=s[i].poz;
for(int i=1;i<=logg[n];i++)
{
int lim=n-(1<<(i-1))+1;
for(int j=1;j<=lim;j++) rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
for(int i=1;i<=n;i++)
{
int st=1,dr=min(n-s[i].poz+1,s[i].poz-1);
while(st<=dr)
{
int mid=(st+dr)/2,ok=0;
int l=1,r=i-1;
while(l<=r)
{
int m=(l+r)/2;
if(get_min(m,i)<=s[i].poz-mid) l=m+1;
else r=m-1;
}
int a=r;
l=i+1;r=n;
while(l<=r)
{
int m=(l+r)/2;
if(get_min(i,m)<=s[i].poz-mid) r=m-1;
else l=m+1;
}
int b=l;
if(1<=a && LCP(s[a].poz,s[i].poz)>=mid) ok=1;
if(b<=n && LCP(s[b].poz,s[i].poz)>=mid) ok=1;
if(ok) st=mid+1;
else dr=mid-1;
}
pas[s[i].poz]=dr;
}
arbint_init(1,1,n);
arbint_update(1,1,n,1,1,cost1);
for(int i=1;i<n;i++)
{
arbint_query(1,1,n,i);
if(pas[i+1]) arbint_update(1,1,n,i+1,i+pas[i+1],sol+cost2);
arbint_update(1,1,n,i+1,i+1,sol+cost1);
}
arbint_query(1,1,n,n);
printf("%d\n",sol);
}
return 0;
}

In    Java  :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int t=0;t<T;t++){
int N = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
String S = sc.next();
System.out.println( buildStringCost(N,A,B,S) );
}
}

public static int buildStringCost(int N, int A, int B, String S){
int[] dp = new int[N];
dp[0] = A;
int lastL = 0;
for(int k=1;k<N;++k){
dp[k] = dp[k-1]+A;
int L = lastL+1;
while(L>0){
String cur = S.substring(k-L+1, k+1);
int idx = S.substring(0, k-L+1).indexOf(cur);
if( -1==idx )
L--;
else{
dp[k] = Math.min(dp[k], dp[k-L]+B);
break;
}
}
lastL = L;
}
return dp[N-1];
}
}

In   C   :

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char s[30001];
int sublens[30001] = { 0 };

void longestsubstr(int pos) {
int i, max = 0;
for (i = 0; i < pos; i++) {
if (s[i] != s[pos]) sublens[i] = 0;
else {
sublens[i] = sublens[i+1] + 1;
if (i + sublens[i] > pos) sublens[i] = pos - i;
if (sublens[i] > max) max = sublens[i];
}
}
sublens[pos] = max;
}

int main() {
int t, t1;
scanf("%d", &t);
for (t1 = 0; t1 < t; t1++) {
int n, a, b, sublen, i, j, temp;
scanf("%d %d %d", &n, &a, &b);
scanf("%s", s);
int ar[30001];
for (i = 0; i < n; i++) {
ar[i] = 0x7FFFFFFF;
sublens[i] = 0;
}
for (i = n - 1; i >= 1; i--) longestsubstr(i);
ar[0] = a;
for (i = 1; i < n; i++) {
if (ar[i-1] + a < ar[i]) ar[i] = ar[i-1] + a;
sublen = sublens[i];
temp = ar[i-1] + b;
for (j = 0; j < sublen; j++) if (temp < ar[i+j]) ar[i+j] = temp;
}
printf("%d\n", ar[n-1]);
}
return 0;
}

In   Python3  :

rep = int(input())
for r in range(rep):
l, a, b = map(int, input().split(' '))
s = input().strip()
i = 1
cost = 0
cost = [float('inf')] * (l + 1)
cost[0] = 0
k = 0
while i <= l: # i is the number of char finished, s[i-1] finished
# find the maximun substring
j = max(i, k)
while j<=l and (s[i-1:j] in s[:i-1]):
j += 1

# s[i-1:j-1] in s

if j-1 != i:
cost[j-1] = min(cost[i-1] + b, cost[j-1])
k = j
cost[i] = min(cost[i-1] + a, cost[i])
#print(cost)
#print(s[i], a)
i += 1

print(cost[-1])```
```

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element