16163번: #15164번_제보, 13275번: 가장 긴 팰린드롬 부분 문자열 - manacher

16163번: manacher 기본 문제.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 4000010;
string S = "$";
int m = -1, k;
int rad[SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    
    string str; cin >> str;
    for(char c : str) S += c, S += '$';
    
    ll ans = 0;
    for(int i=0; i<S.size(); i++)
    {
        if(i <= m) rad[i] = min(m-i, rad[2*k-i]);
        //l = i-rad[i]-1, r = i+rad[i]+1라고 생각하면 편하다. 팰린드롬의 길이를 늘려가며 최대 반지름 길이를 구한다.
        while(0 <= i-rad[i]-1 && i+rad[i]+1 <= S.size() && S[i-rad[i]-1] == S[i+rad[i]+1])
            if(++rad[i] > m-i) m = i+rad[i], k = i;
        ans += (rad[i]+1)/2;
    }
    cout << ans;
}

 

13275번: manacher 기본 문제.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int SIZE = 4000010;
string S = "$";
int m = -1, k;
int rad[SIZE];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    
    string str; cin >> str;
    for(char c : str) S += c, S += '$';
    
    int ans = 0;
    for(int i=0; i<S.size(); i++)
    {
        if(i <= m) rad[i] = min(m-i, rad[2*k-i]);
        while(0 <= i-rad[i]-1 && i+rad[i]+1 <= S.size() && S[i-rad[i]-1] == S[i+rad[i]+1])
            if(++rad[i] > m-i) m = i+rad[i], k = i;
        ans = max(ans, rad[i]);
    }
    cout << ans;
}