sản phẩm tối đa tiền tố chuỗi

Question

Sau đây là một câu hỏi bản demo từ một trang web phỏng vấn mã hóa gọi là codility:

Một tiền tố của một chuỗi S là bất kỳ một phần tiếp giáp hàng đầu của S. Ví dụ, "c" và "cá tuyết "là tiền tố của chuỗi" mã hóa ". Để đơn giản, chúng tôi yêu cầu tiền tố không trống.

Sản phẩm của tiền tố P của chuỗi S là số lần xuất hiện của P nhân với chiều dài của P. Chính xác hơn, nếu tiền tố P bao gồm ký tự K và P xuất hiện chính xác T lần trong S, thì sản phẩm bằng K * T.

Ví dụ, S = "abababa" có các tiền tố sau:

• "a", mà sản phẩm bằng 1 * 4 = 4,
• "ab", mà sản phẩm bằng 2 * 3 = 6,
• "aba", có sản phẩm bằng 3 * 3 = 9,
• "abab", có sản phẩm tương đương với 4 * 2 = 8,
• "Ababa", có sản phẩm tương đương với 5 * 2 = 10,
• "ababab", có sản phẩm tương đương với 6 * 1 = 6,
• "abababa", có sản phẩm bằng 7 * 1 = 7.

Tiền tố dài nhất giống với chuỗi gốc. Mục tiêu là chọn một tiền tố như tối đa hóa giá trị của sản phẩm. Trong ví dụ trên, sản phẩm tối đa là 10.

Dưới đây là giải pháp kém của tôi trong Java yêu cầu thời gian O (N^2). Nó rõ ràng là có thể làm điều này trong O (N). Tôi đã suy nghĩ thuật toán Kadanes. Nhưng tôi không thể nghĩ ra bất kỳ cách nào mà tôi có thể mã hóa một số thông tin ở mỗi bước cho phép tôi tìm giá trị tối đa đang chạy. Bất kỳ ai có thể nghĩ về một thuật toán O (N) cho điều này?

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; 
    } 
} 

Answer 1

Đây là phiên bản O (n log n) dựa trên mảng hậu tố. Có O (n) thuật toán xây dựng cho các mảng hậu tố, tôi chỉ không có sự kiên nhẫn để mã hóa chúng.

Ví dụ đầu ra (đầu ra đây không phải là O (n), nhưng nó chỉ để chứng minh rằng chúng tôi thực sự có thể tính toán tất cả các điểm):

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

Về cơ bản bạn phải đảo ngược chuỗi, và tính toán mảng hậu tố (SA) và tiền tố chung dài nhất (LCP).

Sau đó, bạn di chuyển qua mảng SA để tìm LCP khớp với toàn bộ hậu tố (tiền tố trong chuỗi gốc). Nếu có một kết quả phù hợp, hãy tăng bộ đếm, nếu không đặt lại nó thành 1. Mỗi hậu tố (tiền tố) nhận được một "điểm số" (SCR) tương ứng với số lần nó xuất hiện trong chuỗi gốc.

#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; 
    } 
} 

Hầu hết mã này (đặc biệt là mảng hậu tố và triển khai LCP) tôi đã sử dụng trong một số năm trong cuộc thi. Phiên bản này đặc biệt tôi đã thích nghi từ this one I wrote some years ago.

Answer 2

public class Main { 
    public static void main(String[] args) { 
     String input = "abababa"; 
     String prefix; 
     int product; 
     int maxProduct = 0; 
     for (int i = 1; i <= input.length(); i++) { 
      prefix = input.substring(0, i); 
      String substr; 
      int occurs = 0; 
      for (int j = prefix.length(); j <= input.length(); j++) { 
       substr = input.substring(0, j); 
       if (substr.endsWith(prefix)) 
        occurs++; 
      } 
      product = occurs*prefix.length(); 
      System.out.println("product of " + prefix + " = " + 
       prefix.length() + " * " + occurs +" = " + product); 
      maxProduct = (product > maxProduct)?product:maxProduct; 
     } 
     System.out.println("maxProduct = " + maxProduct); 
    } 
}