XYYX型のパリンドローム数

Question

以下はインタビューの質問です。私が持っていなかったより良い、効率的な答えが期待されたので、私はそれを終わらせなかった。私たちは、文字列内の文字の順序を変更することはできません。私たちは、XとYは、同じ文字列S.

ノートから任意の文字ですパターンXYYXの回文数を見つける必要がある文字列Sを考える

---

XとYのS.値も同じにすることができますが、その位置は、文字列Sでのインデックスが最後の文字列

を内の任意の文字のために異なっている場合にも、2つの文字列が異なっている

文字列Sに異なることが必要です

例：Say stringはS = abbaabです。

abba [Indexes : 1,2,3,4] 
abba [Indexes : 1,2,3,5] 
baab [Indexes : 3,4,5,6] 
baab [Indexes : 2,4,5,6] 

だから、このような回文の数をカウントする方法：、そしてその答えは、このような4つの回文がある4.

です。文字列の長さは1000000まで上がる可能性があります。それを行うにはどうすればよいでしょうか？

Answer 1

質問のディスカッションセクションで見つかるように、目標は「実際の」回文を見つけるのではなく、「X *」が一致する「XYYX *」のようなものです。

これは、Sの各位置で、複数の回文が可能である可能性があるため、入力を繰り返している間に検索状態を維持する必要があることを意味します。

"abbaaaa ...."（abbaから始まり、(1000000 - 4) 'a'文字で終わる）の（最悪の場合？）入力を考えてみましょう。この場合、いくつの状態インスタンスを維持する必要がありますか？ 。。答えはステート・マシンは（状態が維持）に定義されてどのようにビットを依存

が言及したステートマシンは、マッチの検出器であるのは、いくつかのコードを見てみましょう（F＃が選ばれます。）

type PState = 
    | X of char 
    | Y0 of char * char 
    | Y1 of char * char 
    | X1 of char * char 
    | XN of char * char 
    | End 

let tryProgress c = function 
    | X(x) -> Some(Y0(x,c)) 
    | Y0(x,y) -> if c = y then Some(Y1(x,y)) else None 
    | Y1(x,y) -> if c = x then Some(X1(x,y)) else None 
    | X1(x,y) -> if c = x then Some(XN(x,y)) else Some (End) 
    | XN(x,y) -> if c = x then Some(XN(x,y)) else Some (End) 
    | End -> failwith "This instance is done and should have been dismissed." 

let count (s : string) = 
    s.ToCharArray() 
    |> Array.fold (fun (states,counter) c -> 
      let counter1 = ref 0 
      (X(c)) :: (states 
      |> List.map (fun fsm -> 
        let res = tryProgress c fsm 
        // printfn "%A -> %c -> %A" fsm c res 
        match res with 
        | None -> None 
        | Some(X1(x,y)) -> 
         counter1 := !counter1 + 1 
         Some(X1(x,y)) 
        | Some(XN(x,y)) -> 
         counter1 := !counter1 + 1 
         Some(XN(x,y)) 
        | Some(End) -> 
         counter1 := !counter1 + 1 
         None 
        | Some(fsm1) -> Some(fsm1) 
       ) 
      |> List.filter (fun mfsm -> match mfsm with | Some(fsm) -> true | None -> false) 
      |> List.map (fun mfsm -> Option.get mfsm)) 
      , (!counter1 + counter) 
     ) ([],0) 
    |> snd 

let s = "abbaab" 
count s 

(* 
    Yields: 
    val it : int = 4 
    as hoped for. 
*) 

タイプPStateは、それぞれのstに必要なデータとともにステートマシンの個々のステートを記述する識別された共用体ですates。

tryProgress関数は、fからのインスタンスと次の入力文字を取り、Pstate optionという結果を返します。文字が新しい可能な状態にならない場合、この関数はNoneを返します。それ以外の場合はSome <resulting state>を返します。

最後に、count関数は、入力文字列の文字を繰り返し処理し（入力ファイルをchar-wise ...でも読み取ることができます）、tryProgress関数を各アクティブステートマシンに適用します。同様に、どのインスタンスが「忘れる」か、どのインスタンスを維持するかを決定し、発見された疑似回文のカウンタをいつ増やすかを決定します。

最悪の場合の入力シナリオに戻って、保存されるFSMインスタンスの数は文字の数とともに増加し、ケースX = Yも保存される状態の数を減らすのに役立たないためです。これらのインスタンスの大部分は、シーケンスが終了するまで状態XN('a','a')になります。

このように、私は問題を誤ったものとして分類しようとします。 （"aaaaaaa" -> [0,1,2,3;0,1,2,4;0,1,2,5;0,1,2,6; 1,2,3,4; 1,2,3,5; 1,2,3,6; ...]）。

UPDATE

別の言語が今人気のC++バージョンここでは、コードサンプルのために要求されたとおり：

#include <cstdint> 
#include <string> 
#include <list> 
#include <iostream> 
#include <exception> 
#include <stdexcept> 

enum class PStateName 
{ 
    X,Y0,Y1,X1,XN,END,FAIL 
}; 

struct PState 
{ 
    PStateName state; 
    char x; 
    char y; 

    PState(PStateName s, char x0, char y0 = '\0') 
    : state(s) 
    , x(x0) 
    , y(y0) 
    { 

    } 

    static PState MakeX(char x0) 
    { 
     return PState(PStateName::X, x0); 
    } 
    static PState To_Y0(const PState &pre, char y0) 
    { 
     return PState(PStateName::Y0,pre.x, y0); 
    } 
    static PState To_Y1(const PState&pre) 
    { 
     return PState(PStateName::Y1,pre.x,pre.y); 
    } 
    static PState To_X1(const PState&pre) 
    { 
     return PState(PStateName::X1,pre.x,pre.y); 
    } 
    static PState To_XN(const PState&pre) 
    { 
     return PState(PStateName::XN,pre.x,pre.y); 
    } 
    static PState To_End(const PState&pre) 
    { 
     return PState(PStateName::END,pre.x,pre.y); 
    } 
    static PState To_Fail(const PState&pre) 
    { 
     return PState(PStateName::FAIL,pre.x,pre.y); 
    } 
}; 

PState Progress(const PState& current, char c) 
{ 
    switch(current.state) 
    { 
     case PStateName::X: 
      return PState::To_Y0(current,c); 
      break; 
     case PStateName::Y0: 
      if(c == current.y) 
       return PState::To_Y1(current); 
      else 
       return PState::To_Fail(current); 
      break; 
     case PStateName::Y1: 
      if(c == current.x) 
       return PState::To_X1(current); 
      else 
       return PState::To_Fail(current); 
      break; 
     case PStateName::X1: 
      if(c == current.x) 
       return PState::To_XN(current); 
      else 
       return PState::To_End(current); 
      break; 
     case PStateName::XN: 
      if(c == current.x) 
       return PState::To_XN(current); 
      else 
       return PState::To_End(current); 
      break; 
     case PStateName::END: 
      throw std::exception(/*"Instances in state End should have been dismissed and never show here."*/); 
      break; 
     case PStateName::FAIL: 
      throw std::exception(/*"Instances in state FAIL should have been dismissed and never show here."*/); 
      break; 
     default: 
      throw std::exception(/*"Fix me! Unknown state in a switch statement!"*/); 
      break; 
    } 
} 

typedef std::list<PState> StateList; 

StateList nextChar(const StateList& actives, char c, size_t &counter) 
{ 
    StateList result; 
    for(auto fsm : actives) 
    { 
     PState fsm1 = Progress(fsm,c); 
     switch(fsm1.state) 
     { 
      case PStateName::FAIL: // Do nothing - weed out and do not count it. 
       break; 
      case PStateName::X1: 
       counter++; 
       result.push_back(fsm1); 
       break; 
      case PStateName::XN: 
       counter++; 
       result.push_back(fsm1); 
       break; 
      case PStateName::END: 
       counter++; 
       break; 
      default: 
       result.push_back(fsm1); 
       break;    
     } 
    } 

    result.push_back(PState::MakeX(c)); 
    return result; 
} 

size_t countString(const std::string& s) 
{ 
    size_t counter = 0; 
    StateList current; 
    for(auto c : s) 
    { 
     current = nextChar(current,c,counter); 
    } 
    return counter; 
} 

size_t countFile(const std::string& filePath) 
{ 
    size_t counter = 0; 
    StateList current; 
    // TODO: read file char by char and feed it to nextChar as shown in the countString() function. 
    return counter; 
} 


int main(int argc, const char * argv[]) 
{ 
    std::string s("abbaab"); 
    std::cout <<"\"" << s << "\": " << countString(s) << std::endl; 
    return 0; 
}