(16163) #15164번_제보

https://www.acmicpc.net/problem/16163

단계별로 풀어보기

60단계(문자열 알고리즘 2) 2번째

 

 

 

마찬가지로 매내처 알고리즘을 쓰면 된다. 매내처 알고리즘으로 나온 배열의 최대값 대신 배열의 총합을 구하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  string str, str2="#";

  cin >> str;
  
  vector<int> dp(str.length()*2+2);
  
  for(char c:str){
    str2+= c;
    str2+= '#';
  }
  
  int r= 0, p= 0, len= str.length()*2+1;
  long ans= 0;
  
  for(int i=1;i<len;i++){
    if(i<=r)  dp[i]= min(r-i, dp[2*p-i]);

    while(i-dp[i]-1>=0 && i+dp[i]+1<len && str2[i-dp[i]-1]==str2[i+dp[i]+1])  dp[i]++;

    if(r<i+dp[i]){
      r= i+dp[i];
      p= i;
    }
    
    ans+= (dp[i]+1)/2;
  }

  cout << ans;

  return 0;
}