Предположим, вы читаете из потока символов, функция должна вернуться, когда вы прочитали первое вхождение палиндрома.
Длина палиндрома должна быть четным числом.
Требование временной сложности O(N).
Пример:
Одним из приближенных решений, которое в большинстве случаев должно выполняться за линейное время O(n), является использование скользящего хэша.
Вы отслеживаете хэш строки и ее реверс. Каждый раз, когда вы читаете новый символ, вы можете обновлять два хеш-значения в O(1). Затем вы сравниваете два хэша, если они равны, то вы сравниваете строку и ее резерв. Если это также равно, выходит, и вы получили палиндром.
Например, одна очень простая скользящая хэш-функция: 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_rev 32-битным целым числом и выбрать m = 2^32. Затем вы можете игнорировать операцию (mod m).
Вернитесь, когда прочитаете первый символ, это палиндром из одной буквы.
Что вам нужно, так это небольшая модификация алгоритма Манахера. Он позволяет найти все палиндромы в строке за линейное время. Суть алгоритма в том, что он фактически идет слева направо, «используя» новые символы, когда это необходимо. Необходимая модификация заключается в том, что вам нужно читать новый символ, только когда вы пытаетесь получить к нему доступ.
Остановитесь, если вы нашли палиндром, который восходит к началу потока.
Этот (непроверенный код 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;
}
Как насчет использования Hashset?
скажем, входной поток 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.
}
Вот мое мнение. Он сканирует накопленную строку для каждого нового символа начиная с текущей середины строки, поэтому если текущая строка не является палиндромом, произойдет быстрый сбой.
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"));
}
Хорошо, поскольку мой первый ответ имеет временную сложность 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 цифр дает нам числовую систему по основанию 36).
Это решение (в Haskell) основано на наблюдении, что палиндром четной длины содержит повторяющийся символ в центре. Когда мы читаем символы из входного потока, мы проверяем такие пары, и когда они найдены, мы задаем новый ответ-кандидат. Для каждого палиндрома-кандидата мы также храним список «символов, оставшихся для сопоставления», и по мере чтения каждого нового символа мы сопоставляем его с этим списком — без совпадения кандидат отбрасывается. Когда список совпадений пуст, решение найдено. Обратите внимание, что хотя каждый кандидат поддерживает свой собственный список совпадений, все они являются просто суффиксами одного и того же списка, поэтому в Haskell все они будут совместно использовать пространство и в совокупности не будут занимать больше O(n) места, даже если существует много кандидатов.
В лучшем случае, когда в центре ответа находится только один парный символ и, следовательно, нет «ложноположительных» кандидатов, временная сложность равна O (n) — каждый символ проверяется не более двух раз. В случае входной строки со многими ложными запусками, т. Е. «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
