gpt4 book ai didi

algorithm - 最大产品前缀字符串

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:49:31 24 4
gpt4 key购买 nike

以下是来自名为 codility 的编码面试网站的演示问题:

A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty.

The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals K * T.

For example, S = "abababa" has the following prefixes:

  • "a", whose product equals 1 * 4 = 4,
  • "ab", whose product equals 2 * 3 = 6,
  • "aba", whose product equals 3 * 3 = 9,
  • "abab", whose product equals 4 * 2 = 8,
  • "ababa", whose product equals 5 * 2 = 10,
  • "ababab", whose product equals 6 * 1 = 6,
  • "abababa", whose product equals 7 * 1 = 7.

The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 10.

下面是我在 Java 中的糟糕解决方案,需要 O(N^2) 时间。显然可以在 O(N) 中执行此操作。我在想 Kadanes 算法。但我想不出任何方法可以在每一步编码一些信息,让我找到运行最大值。任何人都可以为此想到 O(N) 算法吗?

import java.util.HashMap;

class Solution {
public int solution(String S) {
int N = S.length();
if(N<1 || N>300000){
System.out.println("Invalid length");
return(-1);
}
HashMap<String,Integer> prefixes = new HashMap<String,Integer>();
for(int i=0; i<N; i++){
String keystr = "";
for(int j=i; j>=0; j--) {
keystr += S.charAt(j);
if(!prefixes.containsKey(keystr))
prefixes.put(keystr,keystr.length());
else{
int newval = prefixes.get(keystr)+keystr.length();
if(newval > 1000000000)return 1000000000;
prefixes.put(keystr,newval);
}
}
}
int maax1 = 0;
for(int val : prefixes.values())
if(val>maax1)
maax1 = val;
return maax1;
}
}

最佳答案

这是一个基于后缀数组的 O(n log n) 版本。后缀数组的构造算法有 O(n) 种,我只是没有耐心编写它们。

示例输出(这个输出不是 O(n),但它只是为了表明我们确实可以计算出所有的分数):

4*1 a
3*3 aba
2*5 ababa
1*7 abababa
3*2 ab
2*4 abab
1*6 ababab

基本上您必须反转字符串,并计算后缀数组 (SA) 和最长公共(public)前缀 (LCP)。

然后你向后遍历 SA 数组,寻找匹配整个后缀(原始字符串中的前缀)的 LCP。如果匹配,则增加计数器,否则将其重置为 1。每个后缀(前缀)都会收到一个与其在原始字符串中出现的次数相对应的“分数”(SCR)。

#include <iostream>
#include <cstring>
#include <string>
#define MAX 10050
using namespace std;

int RA[MAX], tempRA[MAX];
int SA[MAX], tempSA[MAX];
int C[MAX];
int Phi[MAX], PLCP[MAX], LCP[MAX];

int SCR[MAX];

void suffix_sort(int n, int k) {
memset(C, 0, sizeof C);

for (int i = 0; i < n; i++)
C[i + k < n ? RA[i + k] : 0]++;

int sum = 0;
for (int i = 0; i < max(256, n); i++) {
int t = C[i];
C[i] = sum;
sum += t;
}

for (int i = 0; i < n; i++)
tempSA[C[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];

memcpy(SA, tempSA, n*sizeof(int));
}

void suffix_array(string &s) {
int n = s.size();

for (int i = 0; i < n; i++)
RA[i] = s[i] - 1;

for (int i = 0; i < n; i++)
SA[i] = i;

for (int k = 1; k < n; k *= 2) {
suffix_sort(n, k);
suffix_sort(n, 0);

int r = tempRA[SA[0]] = 0;
for (int i = 1; i < n; i++) {
int s1 = SA[i], s2 = SA[i-1];
bool equal = true;
equal &= RA[s1] == RA[s2];
equal &= RA[s1+k] == RA[s2+k];

tempRA[SA[i]] = equal ? r : ++r;
}

memcpy(RA, tempRA, n*sizeof(int));
}
}

void lcp(string &s) {
int n = s.size();

Phi[SA[0]] = -1;
for (int i = 1; i < n; i++)
Phi[SA[i]] = SA[i-1];

int L = 0;
for (int i = 0; i < n; i++) {
if (Phi[i] == -1) {
PLCP[i] = 0;
continue;
}
while (s[i + L] == s[Phi[i] + L])
L++;

PLCP[i] = L;
L = max(L-1, 0);
}

for (int i = 1; i < n; i++)
LCP[i] = PLCP[SA[i]];
}

void score(string &s) {
SCR[s.size()-1] = 1;

int sum = 1;
for (int i=s.size()-2; i>=0; i--) {
if (LCP[i+1] < s.size()-SA[i]-1) {
sum = 1;
} else {
sum++;
}
SCR[i] = sum;
}
}

int main() {
string s = "abababa";
s = string(s.rbegin(), s.rend()) +".";

suffix_array(s);
lcp(s);
score(s);

for(int i=0; i<s.size(); i++) {
string ns = s.substr(SA[i], s.size()-SA[i]-1);
ns = string(ns.rbegin(), ns.rend());
cout << SCR[i] << "*" << ns.size() << " " << ns << endl;
}
}

大部分代码(特别是后缀数组和 LCP 实现)我已经在比赛中使用了很多年。这个版本我特别改编自this one I wrote some years ago .

关于algorithm - 最大产品前缀字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32040943/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com