c - 为什么我的程序跑的很慢？

问题描述

问 题

做oj的 检索字符串的题 有几个检查点超时 求看看这个程序哪些部分可以改进节约时间跑的更快 没法用
strlwr
题目是这样的
输入格式：

2 行。
第1 行为一个字符串，其中只含字母，表示给定单词；
第2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

输出格式：
只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

#include <stdio.h>
#include <string.h>
int main(void)
{
    char word[11], arti[1000001];
    gets(word);
    gets(arti);
    int i;

    for (i = 0; word[i] != '\0'; i++) {
        if (word[i] >= 'a')
            word[i] -= 'a' - 'A';
    }
    
    for (i = 0; arti[i] != '\0'; i++) {
        if (arti[i] >= 'a')
            arti[i] -= 'a' - 'A';
    }
    
    strcat(word," ");
    strcat(arti," ");
    
    int p=0,m;
    char *a;
    while(a=strstr(arti,word))
    {
        if(a==arti||*(a-1)==' ')
        {
            if(p==0) 
            m=a-arti;
            p++;
            *a=1;
        }
    }
    
    if(p==0)
    {
        puts("-1");return 0;
    }
    
    printf("%d ",p);
    printf("%d",m);
    return 0;
}

解决方案

string searching的问题暴力求解太慢了，常用的算法有

• KMP

• Rabin–Karp

下面是KMP算法，具体的原理还是去看《算法导论》吧

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void KMPsearch(char *pat, char *txt);
void computerLPS(char *pat, int M, int *lps);


int main(int argc, char *argv[]) {
    char *t = "test string searching text test";
    char *s = "test";
    KMPsearch(s, t);
    return 0;
}


void computerLPS(char *pat, int M, int *lps)
{
    int len, i;  //len用来指示当前LPS的长度
    lps[0] = 0; //当index为0时是epsilon,LPS长度是0
    len = 0;
    i = 1;
    while ( i < M ) { //计算从1到m-1的LPS
        //考虑abababca, 当i进行到5的时候, len=3此时时有最长的LPS aba
        //而p[i] = p[5] = p[len] = b 所以更新LPS为ababab, len=4
        if (pat[i] == pat[len]) {
            len += 1;
            lps[i++] = len;
        }
        //如果p[i] != p[len],那么此时的LPS长度要比到前一个index的LPS长度小
        //将len更新为lps[len-1]
        else {
            //这里的if不需要i++的原因是:
            //要么len一直迭代到0(没有找到一个LPS是以p[i]结尾的),
            //然后转入下个else分支
            //要么找到一个以p[i]结尾的LPS,那么p[i] == p[len],转入上个分支
            if (len != 0) len = lps[len-1];
            else lps[i++] = 0;
        }
    }
}
void KMPsearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int *lps = (int *)malloc(M * sizeof(int));
    computerLPS(pat, M, lps);
    int i = 0;
    int j = 0;
    int count = 0;
    int firstindex = -1;
    printf("txt: %s\npattern: %s\n", txt, pat);
    while (i < N) {
        if (txt[i] == pat[j]) {i++; j++;} //如果匹配继续下一个
        if (j == M ) {
            printf("pattern found at index %d\n", i - M);
            count++;
            j = lps[j-1]; //右移pattern索引
            if (firstindex == -1)
                firstindex = i - M;
        }
        else if (i < N && txt[i] != pat[j]) {
            if (j != 0) j = lps[j-1]; //右移pattern索引;
            else i++; //没有lps
        }
    }
    printf("occur times: %d\nfirstindex: %d\n", count, firstindex);
    free(lps);
}

输出：

txt: test string searching text test
pattern: test
pattern found at index 0
pattern found at index 27
occur times: 2
firstindex: 0

这篇关于c - 为什么我的程序跑的很慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！