题解 | 重复词

#include<bits/stdc++.h>
using namespace std;
class Periods {
public:
    long long getLongest(int n, string s) {
        vector<long long> ans(n, 0);
        char startChar = s[0];
        vector<int> startIndex;
        
        // 找到所有与首字符相同的位置
        for (int i = 1; i < n; i++) {
            if (s[i] == startChar) {
                startIndex.push_back(i);
            }
        }
        
        // 从后向前处理每个可能的起始位置
        for (int i = startIndex.size() - 1; i >= 0; i--) {
            int index = startIndex[i];
            ans[index] = index;
            long long ansTemp = index;
            int temp = 1;
            index++;
            
            while (index < n && (temp + 1) * 2 <= (index + 1) 
                   && s[index] == s[temp]) {
                ans[index] = max(ans[index], ansTemp);
                index++;
                temp++;
            }
        }
        
        // 计算总和
        return accumulate(ans.begin(), ans.end(), 0LL);
    }
};

import java.util.*;

public class Periods {
    public long getLongest(int n, String s) {
        // 初始化答案数组
        long[] ans = new long[n];
        char startChar = s.charAt(0);
        List<Integer> startIndex = new ArrayList<>();
        
        // 找到所有与首字符相同的位置
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == startChar) {
                startIndex.add(i);
            }
        }
        
        // 从后向前处理每个可能的起始位置
        for (int i = startIndex.size() - 1; i >= 0; i--) {
            int index = startIndex.get(i);
            ans[index] = index;
            long ansTemp = index;
            int temp = 1;
            index++;
            
            while (index < n && (temp + 1) * 2 <= (index + 1) 
                   && s.charAt(index) == s.charAt(temp)) {
                ans[index] = Math.max(ans[index], ansTemp);
                index++;
                temp++;
            }
        }
        
        // 计算总和
        long sum = 0;
        for (long val : ans) {
            sum += val;
        }
        return sum;
    }
}

# -*- coding:utf-8 -*-
class Periods:
    def getLongest(self, n, s):
        # 初始化答案数组，记录每个位置的最长重复词长度
        ans = [0 for i in range(n)]
        
        # 获取首字符
        start_c = s[0]
        start_index = []
        
        # 找到所有与首字符相同的位置
        for i in range(1, n):
            if s[i] == start_c:
                start_index.append(i)
        
        # 从后向前处理每个可能的起始位置
        for index in start_index[::-1]:
            ans[index] = index
            ans_temp = index
            temp = 1
            index += 1
            
            # 检查是否可以继续扩展重复词
            while index < n and (temp + 1) * 2 <= (index + 1) and s[index] == s[temp]:
                ans[index] = max(ans[index], ans_temp)
                index += 1
                temp += 1
        
        # 返回所有长度之和
        return sum(ans)