I am getting WA on submission on test-case 15.
APPROACH
Using KMP’s preprocessing Technique, I first find the maximum length of proper prefix of the string that is also the suffix of the string. Let that length be PL, N be the length of the String and REMLEN equals N - L. So according to me the answer should be N + (K - 1) * REMLEN.
CODE
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define max_size 500000
int prefix[max_size];
//char arr[max_size];
void preprocess(std::string& str)
{
prefix[0] = 0;
int i = 1;
int j = 0;
int n = str.length();
//std::cout << "preprocessing" << std::endl;
while(i < n)
{
if(str[i] == str[j])
{
prefix[i] = j + 1;
i++;
j++;
}
else
{
if(j > 0)
{
j = prefix[j - 1];
}
else
{
prefix[i] = 0;
i++;
}
}
}
}
void func(std::string& str,int k)
{
if(str.length() == 0)
{
//printf("%d\n",0);
std::cout << 0 << std::endl;
return;
}
if(k == 1)
{
//printf("%d\n",str.length());
std::cout << str.length() << std::endl;
return;
}
preprocess(str);
int n = str.length();
int prefix_length = prefix[n - 1];
//printf("prefix_length : %d\n",prefix_length);
int remaining_length = n - prefix_length;
long long ans = n + (k - 1) * remaining_length;
//printf("%llu\n",ans);
std::cout << ans << std::endl;
}
int main()
{
int t;
scanf("%d",&t);
while(t > 0)
{
std::string str;
int k;
std::cin >> str;
std::cin >> k;
func(str,k);
t--;
}
return 0;
}