백준
백준 소스코드 [C++] 16900 이름 정하기
Hani_Levenshtein
2020. 10. 27. 19:56
16900번: 이름 정하기
첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
백준 소스코드 [C++] 16900 이름 정하기
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
vector<ll> getPi(string sub) {
vector<ll> pi(sub.size(), 0);
for (int i = 1, j = 0; i < sub.size(); i++) {
while (j > 0 && sub[i] != sub[j]) j = pi[--j];
if (sub[i] == sub[j]) pi[i] = ++j;
}
return pi;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
string target;
ll n;
cin >> target >> n;
vector<ll> res = getPi(target);
cout << n * (ll)target.size() - (ll)res[target.size() - 1] * (n - 1)<<'\n';
return 0;
}