Отримання знань

дистанційна підтримка освіти школярів


Спеллчекер
http://acm.pku.edu.cn/JudgeOnline/problem?id=1035

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1035;
const maxn = 10000;

type integer = longint;
Tstring = string[15];

var a: array[1..maxn] of Tstring;
n: integer;

var st: Tstring;

procedure prepare;
begin
n := 0; readln(st);
repeat
n := n + 1;
a[n] := st;
readln(st);
until st = '#';
end;

function appear(var st: Tstring): boolean;
var i: integer;
begin
appear := true;
for i := 1 to n do if a[i] = st then exit;
appear := false;
end;

function replace(l: integer; var s, t: Tstring): boolean;
var i, sum: integer;
begin
sum := 0;
for i := 1 to l do if s[i] <> t[i] then sum := sum + 1;
replace := (sum = 1);
end;

function more(l: integer; var s, t: Tstring): boolean;
var i: integer;
begin
i := 0;
while (i < l) and (s[1 + i] = t[1 + i]) do i := i + 1;
while (i < l) and (s[1 + i] = t[2 + i]) do i := i + 1;
more := i = l;
end;

procedure find(var st: Tstring);
var len, i, l: integer;
begin
len := length(st);
for i := 1 to n do begin
l := length(a[i]);
if (len = l) and replace(l, st, a[i]) then write(' ', a[i]) else
if (len = l - 1) and more(len, st, a[i]) then write(' ', a[i]) else
if (len = l + 1) and more(l, a[i], st) then write(' ', a[i]);
end;
end;

procedure main;
begin
readln(st);
repeat
if appear(st) then writeln(st, ' is correct')
else begin
write(st, ':');
find(st); writeln;
end;
readln(st);
until st = '#';
end;

begin
prepare;
main;
end.

   Пример решения на С++:

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

#define N 10010
char   dict[N][20];
int    result[N];
int    len;

int  check( char a[20], char b[20] )
{
    int l1= strlen(a), l2= strlen(b);
    int num= 0;
   
    if( l1== l2 )
    {
        for( int i= 0; i< l1; ++i )
        if( a[i]!= b[i] && ++num>= 2 ) return -1;
       
        if( num== 0 )  return 2;
    }
    else if( l1< l2 )
    {
        for( int i= 0, j= 0; i< l1 && j< l2; ++i, ++j )
        if( a[i]!= b[j] )
        {
            if( ++num>= 2 ) return -1;
            i--;
        }
    }
    else
    {
        for( int i= 0, j= 0; i< l1 && j< l2; ++i, ++j )
            if( a[i]!= b[j] )
            {
                if( ++num>= 2 ) return -1;
                j--;
            }
    }

    return 1;
}

int main()
{
    char  str[20];
   
    while( scanf("%s", str), strcmp( str, "#" )!= 0 )  strcpy( dict[len++], str );
    while( scanf("%s", str), strcmp( str, "#" )!= 0 )
    {
        int size= strlen( str );
        int tt= 0;
        bool equal= false;
       
        for( int i= 0; i< len; ++i )
        {
            int ll= strlen( dict[i] );
           
            if( abs( ll- size )< 2  ) 
            {
                int  value= check( dict[i], str );
               
                if( value== 1 )   result[tt++]= i;
                else if( value== 2 )
                {
                    printf("%s is correct\n", str);
                    equal= true;
                   
                    break;
                }
            }
        }
       
        if( !equal )
        {
            printf("%s:", str );
            for( int i= 0; i< tt; ++i )
            printf(" %s", dict[ result[i] ]);
           
            printf("\n");
        }   
    }
   
    return 0;
}
 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)