文字ストリームから読み取ると仮定すると、回文の最初の出現を読み取ったときに関数が返されます。
回文の長さは偶数でなければなりません。
時間計算量の要件は O(N) です。
例：
- 1文字目：4
- 2文字目：1
- 3キャラ目：3
- 4文字目：3
- 5文字目：1
- 6文字目：4、戻る
質問する
1567 次
8 に答える
3
必要なのはManacher's Algorithm のわずかな変更です。これにより、文字列内のすべての回文を線形時間で見つけることができます。アルゴリズムについては、実際には左から右に進み、必要に応じて新しい文字を「使用」します。必要な変更は、アクセスしようとしたときにのみ、新しい文字を読み取る必要があることです。
回文を見つけた場合は、停止してください。これは、ストリームの最初にまでさかのぼります。
于 2012-04-09T06:14:46.820 に答える
3
ほとんどの場合、線形時間 O(n) で実行する必要がある近似ソリューションの 1 つは、ローリング ハッシュを使用することです。
文字列のハッシュとその逆を追跡します。新しい文字を読み取るたびに、O(1) の 2 つのハッシュ値を更新できます。次に、2 つのハッシュを比較し、それらが等しい場合は、文字列とそのリザーブを比較します。これも等しい場合、終了し、回文を取得します。
たとえば、非常に単純なローリング ハッシュ関数は次のとおりです。 hash(ck c(k-1).. c0) = (p^k*ck + p^(k - 1) * c(k - 1) + ... + c0 ) mod m ここで、p は奇素数です。
だから始めてください：
p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1
while True
read c
append c to str
prepend c to str_rev
hash = (hash * p + c) mod m
hash_rev = (hash_rev + p_pow * c) mod m
p_pow = p_pow * p
if hash == hash_rev
if str == str_rev
found str to be the first palindrome
さらに高速化するには、hash と hash_rev を 32 ビット整数に宣言し、m = 2^32 を選択します。次に、 (mod m) 操作を無視できます。
于 2012-04-09T06:58:30.177 に答える
3
最初の文字を読んだら戻ります。これは 1 文字の回文です。
于 2012-04-09T05:24:49.923 に答える
0
わかりました、私の最初の答えにはO(n^2)時間の複雑さがO(n)あるので、要求に応じて、ここに別のものがあります。
class PalindromeDetector {
private static class DetectorImpl {
int firstHalfSum, secondHalfSum;
int size = 0, tensPower = 1;
boolean add(int v) {
if (size % 2 == 1) {
firstHalfSum = firstHalfSum + (secondHalfSum / tensPower) * tensPower;
secondHalfSum = (secondHalfSum % tensPower) * 10 + v;
if (firstHalfSum == secondHalfSum)
return true;
} else {
secondHalfSum = secondHalfSum * 10 + v;
}
size ++;
if (size % 2 == 0)
tensPower *= 10;
return false;
}
}
static boolean isPalindrome(String s) {
if (s == null || s.length() == 0)
return false;
int val = Integer.parseInt(s);
int tensPower = s.length() == 1 ? 1 : (int) (Math.pow(10, s.length() - 1));
DetectorImpl detector = new DetectorImpl();
while (tensPower > 0) {
int digit = val / tensPower;
if (detector.add(digit))
return true;
val = val % tensPower;
tensPower /= 10;
}
return false;
}
}
そして、ここに単体テストがあります：
@Test
public void test() {
assertFalse(PalindromeDetector.isPalindrome("4113"));
assertTrue(PalindromeDetector.isPalindrome("3443"));
assertTrue(PalindromeDetector.isPalindrome("473374"));
assertTrue(PalindromeDetector.isPalindrome("413314"));
}
回答は、入力が10進数で構成されていることを前提としていますが、英数字入力用に簡単に拡張できます（英語のアルファベット+ 10桁で基数36の数値システムが得られると仮定してください）。
于 2012-04-11T20:47:16.157 に答える
0
この (テストされていない C#) コードはそれを実行しますが、O(n^2) になる可能性があると思います。誰でもそれを確認/拒否できますか?
main()
{
string str = "";
char c1;
char c2;
while(true)
{
//has to be even, always get two chars at a time
c1 = GetCharFromStream();
c2 = GetCharFromStream();
str += c1 + c2;
if(isPalindrome(str))
{
Console.WriteLine(str);
return;
}
}
}
bool isPalindrome(string str)
{
if (str.Length % 2 != 0)
throw new InvalidArgumentException("str");
int first = 0;
int last = str.Length - 1;
while(first <= last)
{
if(str[first] != str[last])
return false;
first++;
last--;
}
return true;
}
于 2012-04-09T05:40:11.067 に答える
0
これが私の見解です。現在の string の中央から新しいシンボルごとに蓄積された string をスキャンするため、現在の string が回文でない場合は高速に失敗します。
class PalindromeDetector {
private static class DetectorImpl {
final ArrayList<Character> string = new ArrayList<Character>(32);
boolean addSymbol(char symbol) {
string.add(symbol);
return check();
}
private boolean check() {
if (string.size() < 2)
return false;
int lowBound = string.size() / 2 - 1;
int hiBound = lowBound + 1;
while (lowBound >= 0 && string.get(lowBound) == string.get(hiBound)) {
lowBound --; hiBound ++;
}
return lowBound == -1;
}
}
static boolean isPalindrome(String s) {
DetectorImpl detector = new DetectorImpl();
int index = 0;
while (index < s.length())
if (detector.addSymbol(s.charAt(index++)))
return true;
return false;
}
}
コードの単体テストは次のとおりです。
@Test
public void test() {
assertFalse(PalindromeDetector.isPalindrome("4"));
assertTrue(PalindromeDetector.isPalindrome("44"));
assertFalse(PalindromeDetector.isPalindrome("4343"));
assertTrue(PalindromeDetector.isPalindrome("4334"));
assertFalse(PalindromeDetector.isPalindrome("41331"));
assertTrue(PalindromeDetector.isPalindrome("413314"));
}
于 2012-04-10T16:16:26.480 に答える
0
このソリューション (Haskell で) は、偶数回文の中心に繰り返し文字が含まれているという観測に依存しています。入力ストリームから文字を読み取るときに、そのようなペアをテストし、見つかった場合は、新しい候補の回答をシードします。回文の候補ごとに、「一致する残りの文字」のリストも保持し、新しい文字が読み取られるたびに、このリストと照合します。一致しない場合、候補は破棄されます。一致リストが null の場合、解決策が見つかりました。各候補は独自の一致リストを維持しますが、これらはすべて同じリストのサフィックスにすぎないため、Haskell ではこれらはすべてスペースを共有し、多数の候補がある場合でも全体で O(n) スペースを超えることはないことに注意してください。
回答の中心に対になった文字が 1 つしかなく、したがって「偽陽性」の候補が存在しない最良のケースでは、時間の複雑さは O(n) であり、各文字は 2 回以上検査されません。多くの誤った開始を含む入力文字列の場合、つまり「abbbbbbbbbbbba」の場合、時間の複雑さはわかりません。おそらく O(n) ではありませんが、O(n^2) よりは優れています。候補の中心の位置はmin(k, n-k)どこよりも。k
filter_map::(a -> Maybe a)->[a]->[a]
filter_map op = foldr (maybeCons . op) []
where maybeCons Nothing ys = ys
maybeCons (Just y) ys = y:ys
-- Return the first prefix of the input argument that
-- is an even-length palindrome.
prefix_palindrome::(Eq a)=>[a]->[a]
prefix_palindrome (x:xs) = search [x] [] xs
where search seen ([]:_) _ = seen
search (s:seen) candidates (x:xs) | x == s = search seen' (candidates' ++ [seen]) xs
| otherwise = search seen' candidates' xs
where seen' = (x:s:seen)
candidates' = filter_map extend candidates
where extend (c:cs) | c == x = Just cs
| otherwise = Nothing
于 2012-04-14T01:10:38.320 に答える
0
ハッシュセットを使用するのはどうですか？
入力ストリームが1221.
Hashset = empty;
if(hashset does not contain the inputelement)
{
add to hashset. // 12 will be in the hashset. //413 for your example.
}
else
{
delete from Hashset. // First deletes 2 and then 1. // First deletes 3, then 1 then 4.
if(hashset is empty)
return true; //Hashset is empty. return true.
}
于 2012-04-10T05:05:19.830 に答える