练习题 - 不怕噩梦(字符串匹配)

前言

算法拾遗继续。

题目

问题描述

蚊子最近经常做噩梦,然后就会被吓醒。这可不好。。疯子一直在发愁,然后突然有一天,他发现蚊子其实就是害怕某些事。如果那些事出现在她的梦里,就会害怕。我们可以假定那个害怕的事其实是一个字符串。而她做的梦其实也是一个字符串。

她可以一个晚上一直做梦,所以梦这个字符串会很长,如果其中包含了她所害怕的事情,那么她这天晚上就会害怕。当然一个害怕的事也可能在这天晚上被她梦到很多遍,当然每个晚上也可能有很多种害怕的事都被梦到。

每个害怕的事都有一定的权值。而这天晚上如果梦到了某件事,那么这件事所产生的黑暗效果等于这件事的权值乘以这个害怕的事在梦字符串里的开始位置。如果同样的事梦到了很多遍,那么就重复上面的操作很多遍。当天晚上的黑暗效果总和等于当天所有害怕的事产生的黑暗效果累加到一起。现在疯子想知道蚊子这些天来噩梦的黑暗效果总和是多少。

输入(dream.in)

第1行两个整数N,M代表一共有N天梦和M个害怕的事  
第2行到第M+1行。每行一个字符串ti,代表第I个害怕的事  
第M+2行到第2M+2行。每行一个整数ai.代表第I个害怕的事权值  
第2M+3行到第N+2M+3行。每行一个字符串si,代表第I天的梦

输出(dream.out)

SUM  
SUM=N天里黑暗效果的总和。  
我们保证每天的黑暗效果都小于maxlongint;

样例

dream.in

2 2  
abc  
def
1  
2  
abcdef  
defabc

dream.out

15

提示

1*1+2*4+1*4+2*1=15  
对于数据的把握和时间复杂度的估计是成败的关键。 
如果出现一个梦是:ab  
而害怕的事有a,b,ab,那么a,b,ab都需要参与计算..

数据规模

对于30%的数据 
    N,M<=50 
对于所有的数据  
    N<=200.M<=200. length(si)<=200.length(ti)<=200.ai<=10.

解答

有题目描述容易知道,本题为字符串匹配问题。可基于BM、KMP或者任意经典字符串匹配进行求解。

我的实现方法基于BM字符串匹配算法,具体代码实现如下。

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

FILE *in, *out;
int n, m;
char shi[202][202] = {0}, meng[202][202] = {0};
int quan[202] = {0};
int match[202][202] = {0};
int sum = 0;

void tianjump(int jump[], char y[], int len) {
  int i;
  for (i = 0; i < 256; i++)
    jump[i] = len;
  for (i = 0; i < len - 1; i++)
    jump[(int)y[i]] = len - i - 1;
}

int bm(char x[], char y[]) {
  int xlen, ylen, jump[256] = {0};
  int ans[202] = {0}, top = 0;

  xlen = strlen(x);
  ylen = strlen(y);
  tianjump(jump, y, ylen);

  int i, j, k;
  for (i = ylen - 1; i < xlen;) {
    for (k = i, j = ylen - 1; x[k] == y[j] && j >= 0; k--, j--)
      ;

    if (j < 0) {
      ans[top++] = k + 1 + 1;
      i++;
      return k + 1 + 1;
    } else {
      i += jump[(int)x[i]];
    }
  }

  int tem = 0;
  for (i = 0; i < top; i++)
    tem += ans[i];

  return tem;
}

int main() {
  in = fopen("dream.in", "r");
  out = fopen("dream.out", "w");

  fscanf(in, "%d%d", &n, &m);

  int i;
  for (i = 1; i <= m; i++)
    fscanf(in, "%s", shi[i]);

  for (i = 1; i <= m; i++)
    fscanf(in, "%d", &quan[i]);

  for (i = 1; i <= n; i++)
    fscanf(in, "%s", meng[i]);

  int j;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) {
      match[i][j] = bm(meng[i], shi[j]);
      sum += quan[j] * match[i][j];
    }

  fprintf(out, "%d\n", sum);

  fclose(in);
  fclose(out);

  return 0;
}

后记

虽然觉得真的挺不好的,还是在为之后留作业,也即之后在需要用到BM算法的时候再次回顾BM算法吧。

这次又回顾了一下之前写的BM算法,不得不承认,BM算法的精髓还没有被我完全吸收和理解。所以这次的代码中的BM算法,事实上我只是先了一半。先放出来,也许有人需要参考,或者有人有兴趣指点我。

参考


* cached version, generated at 2018-12-04 06:24:47 UTC.

Subscribe by RSS