OI

【字符串】统计单词数

P1308
因为字符串可能有前缀的空格，所以用scanf会有问题。

直接gets匹配字符串,按空格” “分开，单词hash一下比对即可。

这里要注意的是：strlen()调用时间不是常数级，反复调很容易超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<string.h>
int hash(char a[],int st,int ed){
    int t=1,s=0;
    for(int i=st;i<=ed;i++){
        s+=(a[i]-'a'+1)*t;
        t*=26;
    }
    return s;
}

int main(){
    char a[20],b[1000005];
    int word,first,f=0,s=0,st=0,ed=0,i;
    gets(a);
    gets(b);
    int alen=strlen(a);
    int blen=strlen(b);
    for(i=0;i<alen;i++)
        if(a[i]>='A' && a[i]<='Z')
            a[i]+=-'A'+'a';
    for(i=0;i<blen;i++)
        if(b[i]>='A' && b[i]<='Z')
            b[i]+=-'A'+'a';
    while(a[st]==' '&&st<alen)st++;
    ed=st;
    while(a[ed]!=' '&&ed<alen)ed++;
    word=hash(a,st,ed-1);
    st=0;ed=0;
    while(ed<blen&&st<blen){
        st=ed;
        while(b[st]==' '&&st<blen)st++;
        ed=st;
        while(b[ed]!=' '&&ed<blen)ed++;
        if(hash(b,st,ed-1)==word){
            s++;
            if(f==0){
                first=st;
                f=1;
            }
            
        }
    }
    if(s>0)
      printf("%d %d",s,first);
    else
      printf("-1");
    return 0;
}