問題タブ [palindrome]

私は、CormemのIntroduction to Algorithms 3rd edition（pg 405）から動的計画問題を解決しようとしています。

回文は、同じ前方と後方を読み取るいくつかのアルファベット上の空でない文字列です。回文の例は、すべて長さ1 civic、、、、racecarおよびaibohphobia （回文の恐怖）の文字列です。

与えられた入力文字列のサブシーケンスである最長の回文を見つけるための効率的なアルゴリズムを提供します。たとえば、入力が与えられた場合 character、アルゴリズムはを返す必要がありますcarac。

ええと、私はそれを2つの方法で解決することができました：

最初の解決策：

文字列の最長パリンドロームサブシーケンス（LPS）は、それ自体の最長共通サブシーケンスとその逆です。（シーケンスの最長増加部分列を求める別の関連する質問を解決した後、このソリューションを構築しました）。これは単なるLCSバリアントであるため、O（n²）時間とO（n²）メモリも必要です。

2番目の解決策：

2番目の解決策はもう少し複雑ですが、一般的なLCSテンプレートにも準拠しています。それは次の再発から来ています：

lpsの長さを計算するための擬似コードは次のとおりです。

lpを効果的に構築したい場合は、それでもO（n²）の時間とメモリが必要です（テーブル上のすべてのセルが必要になるため）。LCSのようなメモリの少ないアプローチ（LISはO（n）メモリで解決可能）以外のアプローチで解決できるLISなどの関連する問題を分析して、O（n）メモリで解決できるかどうか疑問に思いました。それも。

LISは、候補のサブシーケンスをリンクすることでこの限界を達成しますが、パリンドロームでは、ここで重要なのはサブシーケンスの前の要素ではなく、最初の要素であるため、より困難です。誰かがそれを行うことが可能かどうか知っていますか、または以前のソリューションはメモリが最適ですか？

重複の可能性：
回文の文字列を確認してください

こんにちは専門家。C ++ / Javaの1行のコードで、ある文字列が別の文字列のpalidromeであるかどうかを確認できるかどうかを尋ねられます。

はいの場合、どのように？

誰でも答えることができます。urビューのThnx。

1. リストの逆を返すreverseと呼ばれる2つの引数を持つ再帰的なProlog述語を取得できますか？

   サンプルクエリと期待される結果：

   /li>

2. 呼び出された2つの引数の再帰的Prolog述語はpalindrome、指定されたリストが回文である場合にtrueを返します。

   期待される結果を含むサンプルクエリ：

   /li>

私は (楽しみのために) 回文を認識するスクリプトの作成に取り組んでいました。これまでのところ、「カヤック」、「レースカー」、「アンナ」、「パナマ運河を計画する男」などで成功しています。

余談ですが、PCRE を使用すると物事がはるかに簡単になることは理解していますが、私は PCRE に精通していません。私の主な目的の 1 つは、回文のチェックの背後にあるアルゴリズムを理解することでした。

次の点についてご回答いただければ幸いです。

• 私が抱えているバグの識別。
• コードをどのように改善できるかについての推奨事項 (私の目には比較的素人っぽく見える $count や $scan_count に頼らずに物事を機能させることができれば幸いです)。

前もって感謝します。

文字列で最も長い回文を見つけようとしていました。力ずくで解決するには O(n^3) 時間かかります。サフィックスツリーを使用した線形時間アルゴリズムがあることを読みました。私は接尾辞ツリーに精通しており、それらを快適に構築できます。構築されたサフィックス ツリーを使用して最長の回文を見つけるにはどうすればよいですか。

これは（再び）インタビューの質問です。

単一に接続されたリンクリストが与えられた場合、リスト内で最大の回文を見つけます。（回文の長さは偶数であると想定できます）

私が行った最初のアプローチは、スタックを使用することでした。最初からリストをトラバースし、文字を押し続けます。スタックの一番上の文字がリンクリストの次の文字と同じであることがわかったら、ポップを開始し（そしてリンクリストポインタをインクリメントし）、一致する文字の数にカウントを設定します。不一致が見つかったら、スタックからポップしたすべての文字をプッシュバックし、プッシュおよびポップ操作を続行します。このメソッドの最悪の場合の複雑さはO（n2）です。たとえば、リンクリストが同じ文字の文字列である場合です。

空間と時間の複雑さを（いくつかの一定の要因によって）改善するために、リンクリストを配列にコピーし、配列内で最大サイズのパリンドロームを見つけることを提案しました。これもO（n2）時間の複雑さとO（n）空間の複雑さを取ります。

私を助けるためのより良いアプローチはありますか？:(

プロローグでこの回文プログラムを試していましたが、ロジックは機能しますが、書き込み操作は機能しません。では、コードの問題は何ですか？

palin(List1):- findrev(List1,[],List2), compare(List1,List2).

3桁の数字を2つ掛けて得られる最大の回文を見つけたい。

私はaとbの両方が999であるところから始め、発生するすべての乗算でaとbをデクリメントしました。

結果は698896、289982、94249、69696...になりました。698896が最初の数字です。現在、私はまだ何が欠けているのかを理解しようとしています。

テキストボックスの文字列からスタックに文字を追加しようとしています。

これまでの私のコードは次のとおりです。

LinkedStackのプッシュアンドポップメソッド

getnext（）メソッドは、listnodesと呼ばれる別のパッケージから取得されます

印刷を+cに変更すると、文字列のすべての文字が印刷されますが、myStackの場合は、文字列がインデックス範囲外のエラーになります。

誰かが私が欠けているものを知っていますか？