Интервью Вопрос: Поиск следующих и предыдущих символов в заданной строке?

Question

У нас есть язык X, который имеет один байт и два байта символов. Этот язык имеет следующие характеристики.

1. Значение однобайтового символа всегда будет меньше или равно 127.
2. В двухбайтовом символе первый байт всегда будет больше 127, а значение второго байта может быть любым.

Проблема в том, что нам дана строка произвольной длины и указатель, указывающий на некоторый байт в строке, и мы должны выяснить, что является предыдущим и следующим символом.

Один простой подход будет начинаться с начала строки, проверяя значение байта и сравнивая указатели, пока мы не достигнем заданного указателя. Но в худшем случае, если указанный указатель указывает на последний байт в данной строке, мы должны пройти через все символы.

Я хотел бы знать, есть ли лучший алгоритм, который будет давать результат в постоянное время независимо от длины строки?

Answer 1

Нет, постоянное время невозможно, так как в худшем случае, по словам Алексея, почти вся строка состоит из байтов с верхним битом, и вам нужно вернуться назад к началу, чтобы узнать, какой из них является первым старшим битом. -байт в первой двухбайтовой последовательности.

Надеюсь, этот патологический случай встречается редко, и вы можете просто отступать на шаг назад, пока не встретите младший байт, и в этом случае вы можете быть уверены, что байт после является началом персонаж. Затем вы можете снова идти вперед, пока не встретите свой первоначальный указатель.

Answer 2

Кажется, в худшем случае нам нужно пройти через всю строку. Просто рассмотрим символы A = 100 и B = 200, C = 201 и следующие строки длиной N:

S1 = ABCBCBC ... BC

S2 = BBCBCBC ... BC

Answer 3

Давайте посмотрим ... Вы уже указываете на символ, который может быть одним или двумя байтами. В последнем случае вы можете быть на первом или втором байте этого символа. Итак, сначала вам нужно знать, находитесь ли вы в начале персонажа или нет. Что еще хуже, второй байт двухбайтового символа может иметь любое значение, поэтому есть вероятность, что все байты больше 127! Это делает противным поиск предыдущего персонажа. Но сначала определите, находитесь ли вы в начале нового персонажа или в середине его.

• Определение начала символа: возвращайтесь назад на один байт, пока не найдете байт, для которого не установлен его старший бит. (Или начало строки.) На основе количества байтов с установленным старшим битом вы узнаете, находитесь ли вы в начале или нет. Нечетное число старших битов, установленных перед текущим байтом, означает, что вам нужно вернуться на один байт назад для текущего символа.

• Определение предыдущего символа: вернуться назад на два байта. Если установлен старший бит, вы его нашли. Если нет, перейдите на один байт вперед.

• Определение следующего символа: проверьте старший бит текущего байта. Если установлено, идите вперед на два байта. В противном случае, только один.

• Определение количества символов означает, что вы переходите к началу строки и проверяете старший бит каждого байта. Если установлено, добавьте один к вашему счетчику и пропустите один байт. Если не установлено, просто добавьте один к вашему счету. К сожалению, вам придется пройти через всю строку.

Я предполагаю, что у вас есть какой-то способ указать начало и конец строки. Если нет, то нет указаний на то, где он начинается и останавливается. (Если вы не используете нулевой байт для указания начала / остановки, в этом случае вы просто не можете пропустить байты, потому что вы можете пропустить такой нулевой байт.)

Есть ли более быстрый способ? Хорошо, если вы знаете начальное / конечное расположение, вы можете рассчитать количество байтов в этой строке. Количество символов будет количеством байтов в этой строке, причем их старшие биты не установлены. Так что указывайте только число байтов меньше 128!

Answer 4

Сканируйте в обратном направлении, пока вы не нажмете два последовательных байта меньше 127 или пока не дойдете до начала строки. Теперь вы можете считать персонажей до того места, где вы находитесь, и до одного после текущего персонажа.

Answer 5

Предполагая, что arr [] похож на строку, а указатель на байт является указателем на INDEX

#include<stdio.h>
#include<stdlib.h>
int find_valid(int);
int arr[]={128,12,128,19,128,127,128,12,32,145,12,223,54,76,23};
int main(){
    int index=1;
    while(index != 0){
    printf("\nEnter the index:");
    scanf("%d",&index);
    if(arr[index] < 128){  // it can be the first byte or the second byte of the Two byte
             if( arr[index -1] < 128 ) printf("\nThis is the first byte in itself"); 
             else // index-1 >= 128
                {
                   int count = find_valid(index-2);
                   if(count%2 == 0) printf("\n This is the second byte of the two bytes:");       
                   else printf("\nThis is the first byte in itself:");
                }
             }
    else{ // it can be the second or the first in the two bytes
           if ( arr[index - 1] < 128 ) printf("\n This is the First byte of the two bytes:");
           else{
                 int count = find_valid(index-2);
                 if(count%2 == 0) printf("\n This is the second byte of the two bytes:");
                 else printf("\nThis is the First byte of the two bytes:");
                }
          }         

    printf("\nHave u seen the result:");
    scanf("%d",&index);}
}

int find_valid(int i){
    int count=0;
    while( (arr[i] > 127) && (i>0) ) { ++count; --i;}
        return count;    
}   

Answer 6

На самом деле вам нужно найти три символа: текущий символ, предыдущий символ и следующий символ.

CurrentChar находится либо в позиции P, заданной указателем, либо в точке P-1. Если позиция P указывает на байт, который больше 127, тогда P - CurrentChar. Если P меньше 127, посмотрите на P-1. Если P-1 больше 127, то CurrentChar равен P-1, в противном случае CurrentChar находится в положении P.

Чтобы получить PreviousChar, посмотрите на CurrentChar - 2, и если он больше 127 PreviousChar = CurrentChar -2, в противном случае PreviousChar = CurrentChar -1

Следующий Чар можно получить, посмотрев на P. Если P больше 127, то следующий символ находится в P + 2. Если P меньше 127, NextChar находится в положении P + 1.

Answer 7

Предыдущая: Резервное копирование 2 байта. Если байт> 127, то это начало символа, в противном случае предыдущий символ начинается со следующего символа.

Далее: Если текущий байт> 127, то следующий символ начинается с 2 байтов, в противном случае следующий символ начинается с 1 байта.

Answer 8

при условии, что вы знаете, как двигаться назад в строке (и при условии, что указатель, который они вам дают, фактически гарантированно соответствует первому байту текущего символа, если он многобайтовый). Просто вернитесь на два байта назад.

Если данные при текущем -2> 127, то предыдущий символ - это последние два байта. если данные с текущим значением -2 <127, то предыдущий символ с текущим значением -1. </p>

Аналогично для следующего персонажа. Если данные при текущем + 1 <127, то это следующий символ, иначе это начало многобитного символа. </p>

Если вы не можете двигаться назад, то нет способа сделать это, если не прочитать всю строку, пока не достигнете текущей позиции. Используйте стек для отслеживания последних двух байтов, когда вы нажимаете текущий адрес, тогда все данные, необходимые для предыдущего символа, находятся в стеке.