HackerRank Build a String Solution

#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;
}

#include <bits/stdc++.h>
using namespace std;

const int MaxLen = 200001;
const int MaxLog = 21;
int lg[MaxLen], tmp[MaxLen];
int S[MaxLen];

struct SuffixArray
{
	int rank [MaxLen], SA[MaxLen], h[MaxLen], D[MaxLen];
	int n, dep , count_rank [MaxLen], f[MaxLog][MaxLen];
	void Build ()
	{
		for(int len = 1; len < n; len <<= 1)
		{
			fill ( count_rank , count_rank + 1 + n, 0);
			for (int i=1;i <=n;++ i)
			++ count_rank [ rank [SA[i]+ len ]];
			for (int i=1;i <=n;++ i)
			count_rank [i]+= count_rank [i -1];
			for (int i=n;i >0;--i)
			D[ count_rank [ rank [SA[i]+ len ]]--] = SA[i];
			fill ( count_rank , count_rank + 1 + n, 0);
			for (int i=1;i <=n;++ i)
			++ count_rank [ rank [SA[i ]]];
			for (int i=1;i <=n;++ i)
			count_rank [i]+= count_rank [i -1];
			for (int i=n;i >0;--i)
			SA[ count_rank [ rank [D[i]]] --] = D[i];
			copy (rank , rank + 1 + n, D);
			rank [SA [1]]=1;
			for (int i=2;i <=n;++ i)
			if(D[SA[i]] != D[SA[i -1]] ||
			D[SA[i]+ len] != D[SA[i -1] + len ])
			rank [SA[i ]]= rank [SA[i -1]]+1;
			else
			rank [SA[i ]]= rank [SA[i -1]];
			if( rank [SA[n]] == n) break ;
		}
	}
	int strsuf (int *p, int *q)
	{
		int ret =0;
		for (; *p == *q; ++p, ++q, ++ ret );
		return ret;
	}
	void CalcHeight ()
	{
		for (int i=1;i <=n;++ i)
		{
			if( rank [i] == 1)
			h[i] = 0;
			else
			if(i == 1 || h[i -1] <= 1)
			h[i]= strsuf (S+i, S+SA[ rank [i] -1]);
			else
			h[i]= strsuf (S+i+h[i -1] -1 ,
			S+SA[ rank [i] -1]+h[i -1] -1)+ h[i -1] -1;
			f [0][ rank [i]]=h[i];
		}
		dep =1;
		for (int len =1; len *2 <=n;len <<=1 , dep ++)
		for(int i=1; i+len *2 -1 <=n;++ i)
		f[dep ][i]= min(f[dep -1][ i],f[dep -1][ i+len ]);
	}
	void init ( int _n) // String Stored in (S +1)
	{
		lg[1] = 0;
		for(int i = 2; i <= _n; i++)
			lg[i] = lg[i/2] + 1;
		n = _n;
		memset (tmp ,0, sizeof ( tmp ));
		for (int i=1;i <=n;++ i)
		++ tmp[S[i ]];
		for (int i=1;i <MaxLen;++ i)tmp [i]+= tmp [i -1];
		for (int i=n;i >0;--i)
		SA[ tmp[S[i]] --]=i;
		rank [SA [1]]=1;
		for (int i=2;i <=n;++ i)
		if(S[SA[i]] != S[SA[i -1]])
		rank [SA[i]] = rank [SA[i -1]]+1;
		else
		rank [SA[i]] = rank [SA[i -1]];
		Build ();
		CalcHeight ();
	}
	inline int lcp( int a, int b)
	{ // lcp of S[a] and S[b]
		if(a == b) return n - a + 1;
		a = rank [a], b = rank [b];
		if(a > b) swap (a, b);
		int d = lg[b - a];
		if ((1 << d) == (b - a)) return f[d][a +1];
		else return min(f[d][a+1] , f[d][b -(1<<d )+1]);
	}
}mySA;

/*  Note
	1. Set MaxLen, MaxLog: length of string, log of it
	2. S[i] > 0 (Can't be zero!)
*/

/*  Eaxmple
	S[1] = 'a';
	S[2] = 'b';
	S[3] = 'a';
	mySA.init(3);
	cout << mySA.lcp(1,3) << endl;
*/

int n;
string s = "xxabab";
int myRank[30001];
int rankToIndex[30001];
int minimal[30001][21];
int INF = 1000000001;
int maxJump[30001];

vector <int> dpIndex;
vector <int> dpValue;
int dp[30001];

int rmq(int L, int R)
{
	int t = 0;
	while((1<<(t+1)) <= R-L+1) t ++;
	return min(minimal[L][t], minimal[R - (1<<t) + 1][t]);
}

bool check(int to, int front)
{

	if(to == front) return true;
	int r = myRank[to];
	//cout << "myRank = " << r << endl;
	{
		int L = 0, R = r, M;
		while(R - L > 1)
		{
			M = (L + R) / 2;
			if(rmq(M, r) <= front)
				L = M;
			else
				R = M;
		}
		//cout << "get : " << L << endl;
		if(L > 0)
		{
			int index = rankToIndex[L];
			//cout << index << endl;
			if(mySA.lcp(n+1-index, n+1-to) >= (to - front)) return true;
		}
	}
	{
		int L = r, R = n+1, M;
		while(R - L > 1)
		{
			M = (L + R) / 2;
			if(rmq(r, M) <= front)
				R = M;
			else
				L = M;
		}
		//cout << "get : " << R <<  endl;
		if(R <= n)
		{
			int index = rankToIndex[R];
			//cout << index << endl;
			if(mySA.lcp(n+1-index, n+1-to) >= (to - front)) return true;
		}
	}
	return false;
}

int MAIN()
{
	int T;
	cin >> T;
	while(T--)
	{
		int A, B, len;
		cin >> len >> A >> B >> s;
		n = s.length();
		for(int i = 0; i < n; i++)
			S[i+1] = s[n-1-i];
		mySA.init(n);
		for(int i = 1; i <= n; i++)
		{
			rankToIndex[mySA.rank[i]] = n+1-i;
			myRank[n+1-i] = mySA.rank[i];
		}
		/*for(int i = 1; i <= n; i++)
			cout << myRank[i] << " ";
		cout << endl;*/

		for(int i = 1; i <= n; i++)
		{
			minimal[i][0] = rankToIndex[i];
		}
		for(int k = 1; k <= 20; k++)
			for(int i = 1; i <= n; i++)
			{
				minimal[i][k] = INF;
				int t = i + (1<<(k-1));
				if(t <= n)
					minimal[i][k] = min(minimal[i][k-1], minimal[t][k-1]);
			}
		for(int i = 1; i <= n; i++)
		{
			int L = 0, R = i, M;
			while(R - L > 1)
			{
				M = (L + R) / 2;
				if(check(i, i - M))
					L = M;
				else
					R = M;
			}
			maxJump[i] = L;
			//cout << i << " : " << L << endl;
		}
		dpValue.clear();
		dpIndex.clear();
		dp[1] = A;
		dpValue.push_back(A);
		dpIndex.push_back(1);
		for(int i = 2; i <= n; i++)
		{
			dp[i] = dp[i-1] + A;
			if(maxJump[i] > 0)
			{
				int L = -1, R = dpValue.size(), M;
				while(R - L > 1)
				{
					M = (L + R);
					if(dpIndex[M] >= i - maxJump[i])
						R = M;
					else
						L = M;
				}
				if(R < dpValue.size())
				{
					dp[i] = min(dp[i], dpValue[R] + B);
				}
			}
			while(dpValue.size() > 0 && dp[i] < dpValue[dpValue.size()-1])
			{
				dpValue.pop_back();
				dpIndex.pop_back();
			}
			dpValue.push_back(dp[i]);
			dpIndex.push_back(i);
		}
		cout << dp[n] << endl;
	}
	
	return 0;
}

int main()
{
	int start = clock();
	#ifdef LOCAL_TEST
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios :: sync_with_stdio(false);
	cout << fixed << setprecision(16);
	int ret = MAIN();
	#ifdef LOCAL_TEST
		cout << "[Finished in " << clock() - start << " ms]" << endl;
	#endif
	return ret;
}

import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*; 
import java.util.*;
import java.util.regex.*;
/*
	  br = new BufferedReader(new FileReader("input.txt"));
	  pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
	  br = new BufferedReader(new InputStreamReader(System.in));
	  pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */


public class Solution {
	private static BufferedReader br;
	private static StringTokenizer st;
	private static PrintWriter pw;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		//int qq = 1;
		//int qq = Integer.MAX_VALUE;
		int qq = readInt();
		for(int casenum = 1; casenum <= qq; casenum++)	{
			int n = readInt();
			int a = readInt();
			int b = readInt();
			String s = nextToken();
			int[] list = new int[n];
			for(int i = 0; i < n; i++) {
				list[i] = s.charAt(i) - 'a';
			}

			int[] dp = new int[n+1];
			Arrays.fill(dp, 1 << 30);
			dp[0] = 0;

			ArrayList<int[]> edges = new ArrayList<int[]>();
			ArrayList<Integer> link = new ArrayList<Integer>();
			ArrayList<Integer> length = new ArrayList<Integer>();
			edges.add(empty(26));
			link.add(-1);
			length.add(0);
			int last = 0;
			for(int i = 0; i < n; i++) {
				
				dp[i+1] = Math.min(dp[i+1], dp[i] + a);
				int len = 0;
				int currSuffixLoc = 0;
				while(currSuffixLoc < edges.size() && i + len < list.length) {
					if(edges.get(currSuffixLoc)[list[i+len]] == -1) {
						break;
					}
					currSuffixLoc = edges.get(currSuffixLoc)[list[i+len]];
					len++;
				}
				
				dp[i+len] = Math.min(dp[i+len], dp[i] + b);
				
				// construct r
				edges.add(empty(26));
				length.add(i+1);
				link.add(0);
				int r = edges.size() - 1;
				int p = last;
				while(p >= 0 && edges.get(p)[list[i]] == -1) {
					edges.get(p)[list[i]] = r;
					p = link.get(p);
				}
				if(p != -1) {
					int q = edges.get(p)[list[i]];
					if(length.get(p) + 1 == length.get(q)) {
						link.set(r, q);
					} 
					else {
						// we have to split, add q'
						edges.add(deepCopy(edges.get(q))); // copy edges of q
						length.add(length.get(p) + 1);
						link.add(link.get(q).intValue()); // copy parent of q
						int qqq = edges.size()-1;
						// add qq as the new parent of q and r
						link.set(q, qqq);
						link.set(r, qqq);
						// move short classes pointing to q to point to q'
						while(p >= 0 && edges.get(p)[list[i]] == q) {
							edges.get(p)[list[i]] = qqq;
							p = link.get(p);
						}
					}
				}
				last = r;
			}
			pw.println(dp[n]);
		}
		exitImmediately();
	}

	public static int[] deepCopy(int[] list) {
		int[] ret = new int[list.length];
		for(int i = 0; i < ret.length; i++) {
			ret[i] = list[i];
		}
		return ret;
	}
	
	public static int[] empty(int len) {
		int[] ret = new int[len];
		Arrays.fill(ret, -1);
		return ret;
	}

	private static void exitImmediately() {
		pw.close();
		System.exit(0);
	}

	private static long readLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private static double readDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	private static int readInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private static String nextLine() throws IOException  {
		if(!br.ready()) {
			exitImmediately();
		}
		st = null;
		return br.readLine();
	}

	private static String nextToken() throws IOException  {
		while(st == null || !st.hasMoreTokens())  {
			if(!br.ready()) {
				exitImmediately();
			}
			st = new StringTokenizer(br.readLine().trim());
		}
		return st.nextToken();
	}
}

# Enter your code here. Read input from STDIN. Print output to STDOUT
def sol():
    N, A, B = map(int, raw_input().strip().split())
    S = raw_input().strip()
    res = [0]*N
    res[0] = A
    maxl = 0
    for i in range(1,N):
        minv = res[i-1] + A
        cp, idx, newl = False, i, 0
        for k in range(maxl,-1,-1):
            if S[i-k:i+1] in S[0:i-k]:
                cp, idx, newl = True, i-k, k+1
                break
        if cp: minv = min(minv, res[idx-1]+B)
        maxl = newl
        res[i] = minv
    print res[-1]
T = int(raw_input().strip())
for x in range(T):
    sol()

// given a string, and the remainder of the string that we are looking for, find the length of the biggest substring we could possibly add
function findBiggestSubstring(string, remainder, min) {
    for (var i=min; i <= remainder.length; i++) {
        if (string.indexOf(remainder.substring(0, i)) == -1) {
            return i - 1;
        }
    }
    return i - 1;
}

// given a string, the cost to add and the cost to copy, determine minimum cost
function calculate(string, costAdd, costCopy) {
    var costPerState = [];
    costPerState[string.length-1] = 0;
    biggestPerState = [];
    var biggest = 0;
    for (var i=0; i < string.length; i++) {
        var substring = string.substring(0, i+1);
        var remainder = string.substring(i+1);
        biggest = findBiggestSubstring(substring, remainder, biggest);        
        biggestPerState[i] = biggest;
    }
    for (var i=string.length-2; i >= 0; i--) {
        var minCost = costAdd + costPerState[i+1];
        for (var j=1; j <= biggestPerState[i]; j++) {
            var cost = costCopy + costPerState[i+j];
            minCost = Math.min(minCost, cost);
        }
        costPerState[i] = minCost;
    }
    return costAdd + costPerState[0];
}

function processData(input) {
    var lines = input.split("\n");
    var cases = lines[0];
    for (var t=0; t < cases; t++) {
        var ints = lines[t*2+1].split(' ');
        var string = lines[t*2+2];
        var result = calculate(string, parseInt(ints[1]), parseInt(ints[2]));
        console.log(result);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

import scala.reflect.ClassTag

class SuffixArray (_s: String) {
  val s = _s :+ 0.toChar
  val n = _s.length
  val alphabet_size = (_s.fold (0.toChar) ( (x, y) => x.max (y))).toInt + 1

  private def counting_sort (m: Int, c: Array[Int], p: Seq[Int], o: Array[Int]): Unit = {
    val cnt:Array[Int] = Array.ofDim (m)
    p.foreach (pi => cnt(c(pi)) = cnt(c(pi)) + 1)
    (1 until m).foreach (i => cnt(i) = cnt(i) + cnt(i-1))
    p.reverseIterator.foreach (pi => {
      cnt(c(pi)) = cnt(c(pi)) - 1
      o(cnt(c(pi))) = pi
    })
  }
  private def build ():Array[Int] = {
    val l = s.length
    var p: Array[Int] = Array.ofDim (l)
    var c = s.map (c => c.toInt).toArray
    var q: Array[Int] = Array.ofDim (l)
    counting_sort (alphabet_size, c, (0 until l), p)
    c(p(0)) = 0
    var m = 0
    for (i <- 1 until l) {
      if (s(p(i)) != s(p(i-1))) {
        m = m + 1
      }
      c(p(i)) = m
    }
    m = m + 1
    var step = 1
    while (step < l) {
      counting_sort (m, c, p.map (v => (v + l - step) % l), q)
      val t1 = p; p = q; q = t1
      q(p(0)) = 0
      m = 0
      for (i <- 1 until l) {
        if (c(p(i)) != c(p(i-1)) || c((p(i) + step) % l) != c((p(i-1) + step) % l)) {
          m = m + 1
        }
        q(p(i)) = m
      }
      m = m + 1
      val t2 = c; c = q; q = t2
      step = 2 * step
    }
    p.slice (1, l)
  }
  val o = build
  private def lcp_build () = {
    var q: Array[Int] = Array.ofDim (n)
    val r: Array[Int] = Array.ofDim (n)
    (0 until n).foreach (i => r(o(i)) = i)
    var l = 0
    for (j <- 0 until n) {
      l = 0.max (l - 1)
      val i = r(j)
      if (i > 0) {
        val k = o(i - 1)
        while ((j + l < n) && (k + l < n) && s(j + l) == s(k + l)) {
          l = l + 1
        }
      } else {
        l = 0
      }
      q(i) = l
    }
    (q, r)
  }
  val (lcp, r) = lcp_build
}

class SegmentTree[T : ClassTag] (_a: Array[T], op: (T, T) => T) {
  val a = _a
  val n = a.length
  val t = Array.ofDim (4 * n)
  private def build (v: Int, l: Int, r: Int): Unit = {
    if (l == r) {
      t(v) = a(l)
    } else {
      val m = (l + r) >> 1
      build (v << 1, l, m)
      build ((v << 1) + 1, m + 1, r)
      t(v) = op (t(v << 1), t((v << 1) + 1))
    }
  }
  build (1, 0, n - 1)
  private def reduce (v: Int, l: Int, r: Int, a: Int, b: Int): T =  {
    if (a == l && b == r) {
      t(v)
    } else {
      val m = (l + r) >> 1
      val x = b.min (m)
      val y = a.max (m + 1)
      val w = 2 * v
      if (a <= x) {
        if (y <= b) {
          op (reduce (w, l, m, a, x), reduce (w + 1, m + 1, r, y, b))
        } else {
          reduce (w, l, m, a, x)
        }
      } else {
        reduce (w + 1, m + 1, r, y, b)
      }
    }
  }
  def reduce (a: Int, b: Int): T = reduce (1, 0, n - 1, a, b)
  def update (i: Int, new_value: T) = {
    var l = 0
    var r = n - 1
    var v = 1
    while (l < r) {
      val m = (l + r) >> 1
      v <<= 1
      if (i <= m) {
        r = m
      } else {
        v += 1
        l = m + 1
      }
    }
    t(v) = new_value
    while (v > 1) {
      v &= ~1
      t(v >> 1) = op (t(v), t(v + 1))
      v >>= 1
    }
  }
}

class ArraySet (_a: Array[Int]) {
  val a = _a
  val n = a.length
  def union (that: ArraySet): ArraySet = {
    val b = Array.ofDim[Int] (n + that.n);
    var i = 0
    var j = 0
    var k = 0
    while (i < n && j < that.n) {
      if (a(i) < that.a(j)) {
        b(k) = a(i)
        i += 1
        k += 1
      } else if (a(i) > that.a(j)) {
        b(k) = that.a(j)
        j += 1
        k += 1
      } else {
        b(k) = a(i)
        i += 1
        j += 1
        k += 1
      }
    }
    while (i < n) {
      b(k) = a(i)
      i += 1
      k += 1
    }
    while (j < that.n) {
      b(k) = that.a(j)
      j += 1
      k += 1
    }
    new ArraySet (b.slice (0, k))
  }
  def binsearch (v: Int) = {
    var l = -1
    var r = n
    while (r - l > 1) {
      val m = (l + r) >> 1
      if (a(m) <= v) l = m else r = m
    }
    l
  }
  def upper (v: Int): Int = {
    val l = binsearch (v)
    if (l < 0) a(0)
    else if (l >= n) Int.MaxValue
    else if (a(l) > v) a(l)
    else if (l + 1 < n) a(l + 1)
    else Int.MaxValue
  }
  def lower (v: Int): Int = {
    val l = binsearch (v)
    if (l < 0) Int.MinValue
    else if (l >= n) a(n - 1)
    else if (a(l) < v) a(l)
    else if (l > 0) a (l - 1)
    else Int.MinValue
  }
}


class SegmentTree2D[T : ClassTag] (_a: Array[T], build_op: (T, T) => T) extends SegmentTree[T] (_a, build_op) {
  private def reduce2d[U] (v: Int, l: Int, r: Int, a: Int, b: Int, extract_op: (T) => U, reduce_op: (U, U) => U): U =  {
    if (a == l && b == r) {
      extract_op (t(v))
    } else {
      val m = (l + r) >> 1
      val x = b.min (m)
      val y = a.max (m + 1)
      val w = 2 * v
      if (a <= x) {
        if (y <= b) {
          reduce_op (reduce2d (w, l, m, a, x, extract_op, reduce_op), reduce2d (w + 1, m + 1, r, y, b, extract_op, reduce_op))
        } else {
          reduce2d (w, l, m, a, x, extract_op, reduce_op)
        }
      } else {
        reduce2d (w + 1, m + 1, r, y, b, extract_op, reduce_op)
      }
    }
  }
  def reduce2d[U] (a: Int, b: Int, extract_op: (T) => U, reduce_op: (U, U) => U): U = reduce2d (1, 0, n - 1, a, b, extract_op, reduce_op)
}


object Solution {
  import scala.io._
  //import scala.collection.immutable.TreeSet
  var lineit:Iterator[String] = Source.stdin.getLines.filterNot(_.isEmpty).flatMap(i => i.split(" "))
  def rs() : String = lineit.next
  def ri() : Int = rs.toInt
  def compute_prefix_function (s: String): Array[Int] = {
    val n = s.length 
    val p = Array.ofDim[Int] (n + 1)
    p(0) = 0
    var k = -1
    for (q <- 1 until n) {
      while (k > 0 && s(k+1) != s(q)) {
        k = p(k)
      }
      if (s(k+1) == s(q)) {
        k += 1
      }
      p(q) = k
    }
    p
  }
  def solve (s: String, n: Int, a: Int, b: Int) = {
    val f = Array.fill (n) (Int.MaxValue)
    f(0) = a
    val t = new SegmentTree[Int] (f, (x, y) => x.min (y))
    val sa = new SuffixArray (s)
    val t2 = new SegmentTree2D[ArraySet] (Array.tabulate (n) (i => new ArraySet (Array (sa.r(i)))), (a, b) => a.union (b))
    val tl = new SegmentTree[Int] (sa.lcp, (x, y) => x.min (y))
    for (i <- 1 until n) {
      val o = sa.o(i)
      //val r = sa.r(o)
      def check (l: Int) = {
        val start = i + 1 - l
        val r = sa.r(start)
        def next (t: ArraySet) = t.upper (r)     // t.from (r + 1).headOption.getOrElse (Int.MaxValue)
        def prev (t: ArraySet) = t.lower (r)    // t.to (r - 1).lastOption.getOrElse (Int.MinValue)
        val v = t2.reduce2d[Int] (0, start - l, (t => next (t)), (a, b) => a.min (b))
        if (v < Int.MaxValue && tl.reduce (r + 1, v) >= l) true        
        else {
          val u = t2.reduce2d[Int] (0, start - l, (t => prev (t)), (a, b) => a.max (b))
          (u > Int.MinValue && tl.reduce (u + 1, r) >= l)
        }
      }
      def binsearch (a: Int, b: Int): Int = {
        if (a >= b) a
        else {
          val m = (a + b + 1) >> 1
          if (check (m)) binsearch (m, b) else binsearch (a, m - 1)
        }
      }
      f(i) = f(i - 1) + a
      val l = binsearch (0, (i + 1) >> 1)
      if (l > 0) {
        f(i) = f(i).min (t.reduce (i - l, i - 1) + b)
      }
      t.update (i, f(i))
    }

    f(n-1)
  }
  def main(args: Array[String]) {
    val nt = ri
    for (t <- 1 to nt) {
      val n = ri
      val a = ri
      val b = ri
      val s = rs
      println (solve (s, n, a, b))
    }
  }
}

var f:array [0..30000] of longint;

procedure process;
        var i,n,m,k,a,b,l,r,rs:longint; s,t:ansistring;
        begin
                readln(n,a,b);
                readln(s);
                for i:=1 to n do f[i]:=a*i;
                for i:=1 to n do
                        begin
                        l:=1; r:=i-1; rs:=0;
                        while l<=r do
                                begin
                                m:=(l+r) div 2;
                                t:=copy(s,i-m+1,m);
                                k:=pos(t,s);
                                if k+m-1<i-m+1 then
                                        begin
                                        if m>rs then rs:=m;
                                        l:=m+1;
                                        end
                                else r:=m-1;
                                end;
                        f[i]:=f[i-1]+a;
                        if rs>0 then
                                if f[i-rs]+b<f[i] then f[i]:=f[i-rs]+b;
                        end;                           
                writeln(f[n]);
        end;

procedure dosth;
        var t:longint;
        begin
                readln(t);
                while t>0 do
                        begin
                        dec(t);
                        process;
                        end;
        end;


begin
        dosth;
end.