C++에서 모든 접미사가 있는 문자열의 유사성 합계

이 문제에서는 문자열 str이 제공됩니다. 우리의 임무는 모든 접미사를 가진 문자열의 유사성의 합을 찾는 프로그램을 만드는 것입니다.

문자열 str의 접미사는 문자열의 시작 문자를 제거하여 생성된 모든 문자열입니다.

문자열의 유사성 str1 및 str2는 두 문자열에 공통적인 가장 긴 접두사의 길이입니다. 예를 들어 str1 ='abbac'이고 str2 ='abb'는 3입니다.

반면 str1 ='abca'이고 str2 ='ca'는 0입니다. 처음부터 계산합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - str ='xyxyx'

출력 -

설명 - 모든 부분 문자열과 모든 접미사가 있는 문자열의 유사성은 -

‘xyxyx’ -> 5
‘yxyx’ -> 0
‘xyx’ -> 3
‘yx’ -> 0
‘x’ -> 1
Sum = 5 + 0 + 3 + 0 + 1 = 9

이 문제를 해결하기 위해 Z-알고리즘을 사용하고 Z-배열을 계산합니다. Z 배열은 문자열의 길이와 같은 길이의 배열입니다. 모든 요소는 str의 접두사를 저장합니다. 아래 프로그램은 구현을 보여줍니다.

예시

#include <bits/stdc++.h>
using namespace std;
void createZArray(string str, int n, int Zarray[]) {
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
            R++;
         Zarray[i] = R - L;
         R--;
      }
      else {
         k = i - L;
         if (Zarray[k] < R - i + 1)
         Zarray[i] = Zarray[k];
         else {
            L = i;
            while (R < n && str[R - L] == str[R])
            R++;
            Zarray[i] = R - L;
            R--;
         }
      }
   }
}
int calSumSimilarities(string s, int n) {
   int Zarray[n] = { 0 };
   createZArray(s, n, Zarray);
   int total = n;
   for (int i = 1; i < n; i++)
      total += Zarray[i];
   return total;
}
int main() {
   string s = "xyxyx";
   int n = s.length();
   cout<<"Sum of similarities of string with all of its suffixes is "<<calSumSimilarities(s, n);
   return 0;
}

출력

Sum of similarities of string with all of its suffixes is 9