{"id":16,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-09-12-%e5%ad%97%e7%ac%a6%e4%b8%b2%e5%93%88%e5%b8%8c\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-09-12-%e5%ad%97%e7%ac%a6%e4%b8%b2%e5%93%88%e5%b8%8c","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-09-12-%e5%ad%97%e7%ac%a6%e4%b8%b2%e5%93%88%e5%b8%8c\/","title":{"rendered":"2020-09-12 \u5b57\u7b26\u4e32\u54c8\u5e0c"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=2569&pid=6<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

It is now far into the future and human civilization is ancient history. Archaeologists from a distant planet have recently discovered Earth. Among many other things, they want to decipher the English language.
They have collected many printed documents to form a dictionary, but are aware that sometimes words are not spelled correctly (typos are a universal problem). They want to classify each word in the dictionary as either correct or a typo. Na\u00efvely, they do this using a simple rule: a typo is any word in the dictionary such that deleting a single character from that word produces another word in the dictionary.
Help these alien archaeologists out! Given a dictionary of words, determine which words are typos. That is,which words result in another word in the dictionary after deleting a single character.
For example if our dictionary is {hoose, hose, nose, noises}. Then hoose is a typo because we can obtain hose by deleting a single \u2019o\u2019 from hoose. But noises is not a typo because deleting any single
character does not result in another word in the dictionary.
However, if our dictionary is {hoose, hose, nose, noises, noise} then the typos are hoose, noises,and noise.<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

The \ufb01rst line of input contains a single integer n, indicating the number of words in the dictionary.
The next n lines describe the dictionary. The ith of which contains the ith word in the dictionary. Each word consists only of lowercase English letters. All words are unique.
The total length of all strings is at most 1 000 000.<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

Display the words that are typos in the dictionary. These should be output in the same order they appear in the input. If there are no typos, simply display the phrase NO TYPOS.<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n

\u3010\u6837\u4f8b1\u3011
5
hoose
hose
nose
noises
noise
\u3010\u6837\u4f8b2\u3011
4
hose
hoose
oose
moose
\u3010\u6837\u4f8b3\u3011
5
banana
bananana
bannanaa
orange
orangers<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n

\u3010\u6837\u4f8b1\u3011
hoose
noises
noise
\u3010\u6837\u4f8b2\u3011
hoose
moose
\u3010\u6837\u4f8b3\u3011
NO TYPOS<\/p>\n

<\/a>\u89e3\u6790<\/h5>\n

\u5b57\u7b26\u4e32\u54c8\u5e0c<\/p>\n

#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing namespace std;<\/span>\nchar<\/span> a[<\/span>2000500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\ntypedef<\/span> unsigned<\/span> long<\/span> long<\/span> ll;<\/span>\nchar<\/span> b[<\/span>2000500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll h[<\/span>2000500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll p[<\/span>2000500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> base=<\/span>31<\/span>;<\/span>\nmap<<\/span>ll,<\/span>int<\/span>><\/span>w;<\/span>\nvector<<\/span>int<\/span>><\/span>q;<\/span>\nll get<\/span>(<\/span>ll l,<\/span>ll r)<\/span>\n{<\/span>\n    \/\/cout<\n    return<\/span> h[<\/span>r]<\/span>-<\/span>h[<\/span>l-<\/span>1<\/span>]<\/span>*<\/span>p[<\/span>r-<\/span>l+<\/span>1<\/span>]<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ios:<\/span>:<\/span>sync_with_stdio<\/span>(<\/span>false)<\/span>;<\/span>\n    cout.<\/span>tie<\/span>(<\/span>NULL<\/span>)<\/span>;<\/span>\n    int<\/span> n;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span>\n    a[<\/span>0<\/span>]<\/span>=<\/span>' '<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span> i<=<\/span>n;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>b)<\/span>;<\/span>\n        b[<\/span>strlen<\/span>(<\/span>b)<\/span>+<\/span>1<\/span>]<\/span>=<\/span>'\u0000'<\/span>;<\/span>\n        b[<\/span>strlen<\/span>(<\/span>b)<\/span>]<\/span>=<\/span>' '<\/span>;<\/span>\n        strcat<\/span>(<\/span>a,<\/span>b)<\/span>;<\/span>\n    }<\/span>\n    p[<\/span>0<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>a[<\/span>i]<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>' '<\/span>)<\/span>\n        {<\/span>\n            q.<\/span>push_back<\/span>(<\/span>i)<\/span>;<\/span>\n            if<\/span>(<\/span>i!=<\/span>0<\/span>)<\/span>\n                w[<\/span>h[<\/span>i-<\/span>1<\/span>]<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            h[<\/span>i]<\/span>=<\/span>h[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>base+<\/span>a[<\/span>i]<\/span>-<\/span>'a'<\/span>+<\/span>1<\/span>;<\/span>\n        }<\/span>\n        if<\/span>(<\/span>i!=<\/span>0<\/span>)<\/span>\n        p[<\/span>i]<\/span>=<\/span>p[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>base;<\/span>\n    }<\/span>\n    int<\/span> flag=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>q.<\/span>size<\/span>(<\/span>)<\/span>-<\/span>1<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        for<\/span>(<\/span>int<\/span> j=<\/span>q[<\/span>i]<\/span>+<\/span>1<\/span>;<\/span>j<<\/span>q[<\/span>i+<\/span>1<\/span>]<\/span>;<\/span>j++<\/span>)<\/span>\n        {<\/span>\n            ll sum2=<\/span>h[<\/span>j-<\/span>1<\/span>]<\/span>*<\/span>p[<\/span>q[<\/span>i+<\/span>1<\/span>]<\/span>-<\/span>j-<\/span>1<\/span>]<\/span>+<\/span>get<\/span>(<\/span>j+<\/span>1<\/span>,<\/span>q[<\/span>i+<\/span>1<\/span>]<\/span>-<\/span>1<\/span>)<\/span>;<\/span>\n            if<\/span>(<\/span>w[<\/span>sum2]<\/span>)<\/span>\n            {<\/span>\n                for<\/span>(<\/span>int<\/span> k=<\/span>q[<\/span>i]<\/span>+<\/span>1<\/span>;<\/span>k<<\/span>q[<\/span>i+<\/span>1<\/span>]<\/span>;<\/span>k++<\/span>)<\/span>\n                {<\/span>\n                    printf<\/span>(<\/span>\"%c\"<\/span>,<\/span>a[<\/span>k]<\/span>)<\/span>;<\/span>\n                }<\/span>\n                printf<\/span>(<\/span>\"n\"<\/span>)<\/span>;<\/span>\n                flag=<\/span>0<\/span>;<\/span>\n                break<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    if<\/span>(<\/span>flag)<\/span>\n    {<\/span>\n        printf<\/span>(<\/span>\"NO TYPOSn\"<\/span>)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-16","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/16","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=16"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/16\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=16"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=16"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=16"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}