# 1819: [JSOI]Word Query电子字典

## 1819: [JSOI]Word Query电子字典

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 729  Solved: 238

[Submit][Status]

## Sample Input

4 3 abcd abcde aabc abced abcd abc abcdd

-1 2 3

## HINT

abcd在单词表中出现过；abc与单词abcd、aabc的编辑距离都是1；abcdd与单词abcd、abcde、abced的编辑距离都是1。

## Source

JSOI第二轮Contest1

```  1 /**************************************************************
2     Problem: 1819
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:856 ms
7     Memory:22080 kb
8 ****************************************************************/
9
10 type
11     point=^node;
12     node=record
13                ex:longint;
14                next:array['A'..'Z'] of point;
15                chi,bro:point;
16                ct:char;
17     end;
18 var
19    i,j,k,l,m,n,TP:longint;
21    s1:ansistring;
22 function getpoint:point;inline;
23          var p:point;c1:char;
24          begin
25               new(p);
26               p^.ex:=0;p^.chi:=nil;
27               p^.bro:=nil;
28               for c1:='A' to 'Z' do p^.next[c1]:=nil;
29               exit(p);
30          end;
32           begin
33                if p^.next[c1]<>nil then exit;
34                p^.next[c1]:=getpoint;
35                p^.next[c1]^.ct:=c1;
36                p^.next[c1]^.bro:=p^.chi;
37                p^.chi:=p^.next[c1];
38           end;
40           var
41              p:point;i:longint;
42           begin
44                for i:=1 to length(s1) do
45                    begin
47                         p:=p^.next[s1[i]];
48                    end;
49                p^.ex:=1;
50           end;
52          var p:point;i:longint;
53          begin
55               for i:=1 to length(s1) do
56                   begin
57                        if p^.next[s1[i]]=nil then exit(false);
58                        p:=p^.next[s1[i]];
59                   end;
60               if x=0 then exit(not(p^.ex=0));
61               if (p^.ex>0) and (p^.ex<>tp) then
62                  begin
63                       p^.ex:=tp;
64                       exit(true)
65                  end
66               else exit(false);
67          end;
68 function more(s1:ansistring):longint;
69          var
70             p:point;i,j,k,l:longint;
71          begin
72               inc(tp);
74               for i:=1 to length(s1) do
75                   begin
76                        if exist(p,copy(s1,i+1,length(s1)-i),1) then inc(l);
77                        if p^.next[s1[i]]=nil then exit(l);
78                        p:=p^.next[s1[i]];
79                   end;
80               exit(l);
81          end;
82 function just(s1:ansistring):longint;
83          var p,P1:point;i,j,k,l:longint;
84          begin
85               inc(tp);
87               for i:=1 to length(s1)-1 do
88                   begin
89                        p1:=p^.chi;
90                        while p1<>nil do
91                              begin
92                                   if exist(p1,copy(s1,i+1,length(s1)-i),1) then inc(l);
93                                   p1:=p1^.bro;
94                              end;
95                        if p^.next[s1[i]]=nil then exit(l);
96                        p:=p^.next[s1[i]];
97                   end;
98               if p^.chi=nil then exit(l);
99               p1:=p^.chi;
100               while p1<>nil do
101                     begin
102                          if (p1^.ex>0) and (p1^.ex<>tp) then inc(l);
103                          p1:=p1^.bro;
104                     end;
105               exit(l);
106          end;
107 function less(s1:ansistring):longint;
108          var p,p1:point;i,j,k,l:longint;
109          begin
110               inc(tp);
112               for i:=1 to length(s1) do
113                   begin
114                        p1:=p^.chi;
115                        while p1<>nil do
116                              begin
117                                   if exist(p1,copy(s1,i,length(s1)-i+1),1) then inc(l);
118                                   p1:=p1^.bro;
119                              end;
120                        if p^.next[s1[i]]=nil then exit(l);
121                        p:=p^.next[s1[i]];
122                   end;
123               p1:=p^.chi;
124               while p1<>nil do
125                     begin
126                          if (p1^.ex>0) and (p1^.ex<>tp) then inc(l);
127                          p1:=p1^.bro;
128                     end;
129               exit(l);
130          end;
131 begin
132
135      for i:=1 to n do
136          begin
139          end;
140      tp:=2;
141      for i:=1 to m do
142          begin
144               s1:=upcase(s1);
145               if exist(head,s1,0) then
146                  begin
147                       writeln(-1);
148                       continue;
149                  end;
150               writeln(more(s1)+just(s1)+less(s1));
151          end;
152
153 end.```

251 篇文章37 人订阅

0 条评论

## 相关文章

### Sqoop切分数据的思想概况

Sqoop通过--split-by指定切分的字段，--m设置mapper的数量。通过这两个参数分解生成m个where子句，进行分段查询。因此sqoop的spl...

19950

### Leetcode 65 Valid Number DFA有限状态机

Validate if a given string is numeric. Some examples: "0" => true " 0.1 " =>...

25860

### 第10-11周Python学习周记

3.时间允许的话，尽可能了解一些身为程序员必要掌握的知识（例如json，参考于网络资源）。

14210

8310

14250

17940

22170

19600

35860

### php pathinfo()的用法

pathinfo — 返回文件路径的信息  mixed pathinfo ( string \$path [, int \$options = PATHINFO_D...

41770