чтение пароля

Question

Мне нужно написать алгоритм, который читает поток клавиатуры, пока не получит правильный пароль.

, как если бы пароль был ababac, , а вход - abababa, это означает, что пока он читает ababa, и теперь он ждет, когда c будет разблокирован, если f вместо c, то он перезапустит свой процесс.

это легко сделать в O (n^2), но мой учитель хочет, чтобы мы сделали это в O (n) W.C, можно ли это сделать в этой сложности ?!

Answer 1

Для этого вы можете построить automaton.

Для этого подхода вы можете использовать Aho–Corasick - создать автомат данных для строки и начать подавать его с текстом ввода до тех пор, пока вы не достигнете его конца [не принимаете], или вы достигли принимающего состояния в автомате ,

Ахо-Corasick линейна в шаблоне [пароль] и размера входных данных, так что вы получите O(m+n)

Answer 2

password = "ababac" 
index = 0 
while index < password.length 
{ 
    read character into x 
    if(x == password[index]) 
    index++; 
} 

cout << "congrads!!! you got the password!!"; 

Answer 3

Наивный подход будет хранить вход в круговом char буфер и использовать пользовательские strcmp(), чтобы проверить, содержит ли пароль. Этот метод находится в O (n).

Answer 4

Я думаю, что онлайн-версия Knuth-Morris-Pratt algorithm выполнит эту работу. Однако вам придется хранить и вычислять индексный массив (дополнительная O (n) память в случае реализации циклического массива).

Answer 5

это ближайший я получил Linear время ...

#include<stdio.h> 
#include<stdlib.h> 
#include<dos.h> 
#include<string.h> 

typedef struct node_t { 
    char c; 
    struct node_t * next; 
    struct node_t * prev; 
} node; 


void pop(); 
void printIT(node *p); 
void fixList(); 
char addToList(char c); 
long silence_keyboard(char pw[] ,int size); 

char pw[256]; 
node *head = NULL; 
node *tail = NULL; 
int i = 0 , listSize = 0; 



void main(void) 
{ 
    printf("Set PW:"); 
    scanf("%s",pw); 
    printf("Enter PW (silence_keyboard is activated):\n"); 
    printf("\npw was entered.",silence_keyboard(pw,strlen(pw))); 
} 


long silence_keyboard(char pw[] ,int size) { 
    while (i<size) { 
     for (; i<size && addToList(getche())==pw[i] ; i++); 
     if (i<size) fixList(); 
    } 
    return 0; 
} 

char addToList(char c) { 
    node *temp=(node *)malloc(sizeof(node)); 
    if (!temp) exit(1); 
    temp->c=c; 
    temp->next=NULL; 
    temp->prev=tail; 
    if (!tail) head=temp; 
    else tail->next=temp; 
    tail=temp; 
    listSize++; 
    return c; 
} 

void fixList() { 
    node *p=tail; 
    int j; 
    while (1) { 
     for (; i>=0 && pw[i]!=tail->c ; i--) { 
      pop(); 
      printf("\nso far:"); 
      printIT(head); 
      printf(" pw:%s\n",pw); 
     } 
     for (p=tail,j=i ; j>=0 && pw[j]==p->c ; j-- , p=p->prev); 
     if (j<0) break; 
     else { 
      pop(); 
      printf("\nso far:"); 
      printIT(head); 
      printf(" pw:%s\n",pw); 
      i--; 
     } 
    } 
    i=listSize; 
} 

void printIT(node *p) { 
    if (p) { 
     printf("%c",p->c); 
     printIT(p->next); 
    } 
    else { 
     printf("\n"); 
     return; 
    } 

} 

void pop() { 
    node *p=head; 
    if (!head) return; 
    if (head==tail) tail=NULL; 
    head=head->next; 
    free(p); 
    listSize--; 
}