【洛谷1308】统计单词数

2018-02-18 18:39:17


慎用python……
原题: 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。

现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章

中的某一独立单词在不区分大小写的情况下完全相同(参见样例1 ),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2 )。

1≤ 单词长度≤10。

1≤ 文章长度≤1,000,000

我作为一个高三考生花了一下午写寒假作业的时间搞这种题……
核心思想是在两个串前后都加上一个空格,这样就很开心地不用考虑各种空格问题了,然后直接匹配即可 很妙的思路,应该记录一下
(有一个小问题是注意要把换行符给去掉
这个题解到这就没了,然而对于我来说没完
我首先没有想出来这个思路,于是决定偷懒用python,然后看题解(对我又看题解了,实力这么菜理所应当),发现这个思路后又没有意识到此时cpp也能随便写
然后就被python坑惨了
原因就是python内置的count函数不能统计重叠的子串……
那么当两个需要查找的单词相邻的时候中间的空格就重叠了(开始的时候给单词两段加了空格
python就会统计不到
解决办法就是自己写一个就得了,因为数据量很小也不用kmp,每次find到之后往后挪一格即可
还没完,为啥我会搞一下午?
因为windos和linux跑出来的第二个子问题的结果应该是不一样的,然后我一直纠结在第二个子问题上
(对我又看数据了,实力菜理所应当
收获还是挺多的,最大的收获大概就是我还是别写OI题老实回去搞高考吧hhh
记录python操作:
a.find(b)找到b在a第一次出现的位置,没有返回-1
a.find(b, i)从下表i开始找
a.count(b),统计b在a中出现次数,子串有重叠则使用不可
a.lower()将a中的大写字母全变小写,upper()相反 replace很好用
代码:


import sys

sys.stdin = open("test.in","r")

a = ' ' + sys.stdin.readline().lower().replace('\n','').replace('\r','') + ' '
b = ' ' + sys.stdin.readline().lower().replace('\n','').replace('\r','') + ' '
'''
print a
print b
'''

if b.count(a) == 0 :
        print -1
else :
        i = 0
        bwl = 0
        while True:
                j = b.find(a, i)
                if j == -1:
                        break

                i = j + len(a) - 1
                bwl = bwl + 1

        print bwl, b.find(a)

sys.stdin.close()