无限

[题解]洛谷P1308:统计单词数
原题链接:P1308 统计单词数我为什么这么水……这种程度的题其实是不用写题解的……但是还是水一篇好了。题目非常简...
扫描右侧二维码阅读全文
26
2019/03

[题解]洛谷P1308:统计单词数

原题链接:P1308 统计单词数

我为什么这么水……


这种程度的题其实是不用写题解的……但是还是水一篇好了。

题目非常简单,轻松的字符串匹配,甚至可以应用strchr()函数简单水过,但是那样就不好玩了没有训练意义了,所以我选择用getchar()强制在线搞,仅仅保存模式串。

不难想到以单词为单位进行处理,比较字符串即比较各位置字符。这时有一个显而易见的优化:如果待匹配文本中某个单词在某一位置就已经可以确定失配,那么就没必要继续比较下去,直接跳过这个单词即可。

依据上述思路设计算法,引入一个skip变量保存当前单词是否已经确认要跳过,时间复杂度上界为O(输入文件长度)。在实际情况中,由于待匹配文本的所有单词都不失配的可能性微乎其微,所以实践性很好。

轻松水过 -> R17614035

#include<cstdio>
#include<cstring>
char exp[13];
int len=0;
int main(){
    freopen("test.txt","r",stdin);
    memset(exp,0,sizeof(exp));
    char ch=getchar();
    while(ch!='\r'&&ch!='\n'){
        if(ch>='A'&&ch<='Z')ch=ch-'A'+'a';
        exp[len++]=ch;
        ch=getchar();
    }
    //printf("%s %d\n",exp,len);
    while(ch=='\r'||ch=='\n')ch=getchar();
    int cur=0;
    int pos=0;
    int ans=-1;
    int cnt=0;
    bool skip=false;
    while(ch!='\r'&&ch!='\n'&&ch!=EOF){
        printf("pos %02d :%c\n",pos,ch);
        if(ch==' '){
            if(cur==len){
                cnt++;
                if(ans<0)ans=pos-len;
            }
            cur=0;
            skip=false;
        }else if(!skip){
            if(ch>='A'&&ch<='Z')ch=ch-'A'+'a';
            if(ch==exp[cur])cur++;
            else{
                cur=0;
                skip=true;
            }
        }
        ch=getchar();
        pos++;
    }
    if(cnt){
        printf("%d %d\n",cnt,ans);
    }else{
        puts("-1");
    }
    fclose(stdin);
    return 0;
}

(调试语句未删)

最后修改:2019 年 03 月 26 日 07 : 51 PM

发表评论