5

以下は、codility というコーディング インタビュー サイトからのデモの質問です。

文字列 S の接頭辞は、S の先頭の連続部分です。たとえば、「c」と「cod」は、文字列「codility」の接頭辞です。簡単にするために、プレフィックスは空ではない必要があります。

文字列 S のプレフィックス P の積は、P の出現回数に P の長さを掛けたものです。より正確には、プレフィックス P が K 文字で構成され、P が S 内でちょうど T 回出現する場合、積は K * T に等しくなります。

たとえば、S = "abababa" には次の接頭辞があります。

  • 「a」、その積は 1 * 4 = 4 に等しい、
  • 「ab」、その積は 2 * 3 = 6 に等しい、
  • 「aba」、その積は 3 * 3 = 9 に等しく、
  • 「abab」、その積は 4 * 2 = 8 に等しい、
  • その積が 5 * 2 = 10 に等しい「アババ」、
  • 「ababab」、その積は 6 * 1 = 6 に等しく、
  • 「アババ」、その積は 7 * 1 = 7 です。

最長のプレフィックスは元の文字列と同じです。目標は、製品の価値を最大化するような接頭辞を選択することです。上記の例では、最大積は 10 です。

以下は、O（N ^ 2）時間を必要とするJavaでの私の貧弱なソリューションです。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;
    }
}
4

3 に答える 3

2

これは、接尾辞配列に基づく 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) と最長共通プレフィックス (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 の実装) は、私が数年間コンテストで使用してきたものです。このバージョンは特に、私が数年前に書いたものを改作したものです。

于 2015-08-17T01:45:32.047 に答える
0

私はこの課題に4日以上取り組み、多くのドキュメントを読んで、 O(N) で解決策を見つけました。

私は 81% を得ました。アイデアはウィンドウ スライドを使用した単純なものです。

def solution(s: String): Int = {

var max = s.length  // length of the string 
var i, j = 1  // start with i=j=1 ( is the beginning of the slide and j the end of the slide )
val len = s.length // the length of the string 
val count = Array.ofDim[Int](len)  // to store intermediate results 

while (i < len - 1 || j < len) {
  if (i < len && s(0) != s(i)) {
    while (i < len && s(0) != s(i)) {  // if the begin of the slide is different from 
                                      // the first letter of the string skip it 
      i = i + 1
    }
  }
  j = i + 1
  var k = 1


  while (j < len && s(j).equals(s(k))) { // check for equality and update the array count 
    if (count(k) == 0) {
      count(k) = 1
    }
    count(k) = count(k) + 1
    max = math.max((k + 1) * count(k), max)
    k = k + 1
    j = j + 1
  }

  i = i + 1

}

max // return the max

}

于 2019-06-26T12:44:50.890 に答える