POJ3267The Cow Lexicon(AC)

本文主要是介绍POJ3267The Cow Lexicon(AC)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

2

//牛也有自己的语言，但是有时候会有多余的字母，因为需要去掉最少的字母，然后找到需要的单词
//动态规划不是自己擅长的题目
//这个应该也是要用到字符串匹配了，建个树吧//动态规划自己不擅长，主要是状态方程应该怎么定
//2种方法从前往后和从后往前都AC#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <malloc.h>int W = 0;
int L = 0;#define MAXL 305
#define MAXW 605char word[MAXL];
char dictionary[MAXW][MAXL];typedef struct node
{char word[MAXL];int isword;node* next[26];
}nodes;nodes* trees;nodes* head = NULL;
int dp[MAXL];void init()
{int i = 0;int j = 0;for (i = 0; i < MAXW;i++){for (j = 0; j < MAXL; j++){dictionary[i][j] = '\0';}}for (i = 0; i < MAXL; i++){word[i] = '\0';dp[i] = 0;}return;
}int strlength(char* s)
{int size = 0;while ('\0'!= *s){s += 1;size += 1;}return size;
}void maketree(int index)
{nodes* p = NULL;nodes* tmp = NULL;int size = 0;int i = 0;int j = 0;int nextword = 0;size = strlength(dictionary[index]);p = head;for (i = 0; i < size;i++){nextword = dictionary[index][i] - 'a';if (NULL == p->next[nextword])//没有过这个字母，那就要重新创建{p->next[nextword] = (nodes*)malloc(sizeof(nodes));if (i == size-1){p->next[nextword]->isword = 1;for (j = 0; j < size; j++){p->next[nextword]->word[j] = dictionary[index][j];}p->next[nextword]->word[size] = '\0';}else{p->next[nextword]->isword = 0;p->next[nextword]->word[0] = '\0';}for (j = 0; j < 26; j++){p->next[nextword]->next[j] = NULL;}}else{if (i == size - 1){p->next[nextword]->isword = 1;for (j = 0; j < size; j++){p->next[nextword]->word[j] = dictionary[index][j];}p->next[nextword]->word[size] = '\0';}}p = p->next[nextword];}return;
}int min(int a, int b )
{if (a<=b){return a;}else{return b;}
}int main()
{int i = 0;int j = 0;int k = 0;int len = 0;int pw = 0; //输入单词的位置int pd = 0; //字典单词的位置init();freopen("input.txt","r",stdin);scanf("%d %d",&W,&L);scanf("%s",word);//先创建一个根节点head =(nodes*) malloc(sizeof(nodes));head->word[0] = '\0';head->isword = 0;for (i = 0; i < 26;i++){head->next[i] = NULL;}for (i = 1; i <= W;i++){scanf("%s",dictionary[i]);//maketree(i); //字典树建好了}//动态规划，这个状态方程好难啊。。。//从别人的解题报告中得到的思路，自己不会推状态方程//dp[i]表示从s的第0个字符开始长度为i的字符串(末位为i-1，后面的字符不考虑)需要删除的字符数//貌似没用到字典树，因为单词长度比较短//为什么要从尾部开始比，我比较奇怪//我自己决定从前往后不是更好理解吗？//从尾部找起/*for (i = L - 1; i >= 0;i--){dp[i] = dp[i+1] + 1;  //最差的情况是新的序列多的字母删掉for (j = 1; j <= W;j++) //开始遍历字典{len = strlength(dictionary[j]); //长度//挨个比较字符是否匹配//查看是否有字符串是匹配的，当然中间可能是有些字符是多余的那就要删掉if (len<=(L-i) &&(dictionary[j][0] == word[i])) //长度小于等于我们现在新增的，然后字典那个单词要一致{//这个比较的地方自己也是有点犹豫了pw = i; //从i开始一直到L-1pd = 0;while (pw<L){//找到匹配的单词，那字典就可以移一位if (dictionary[j][pd] == word[pw]){pd += 1;}pw+=1;if (pd == len) //找到单词匹配{dp[i] = min(dp[i], (dp[pw] + pw-i-len)); //pw-i-len表示 pw -i 表示移动了多长的字符串，然后匹配到len的字符，因为中间可能会有多的字符break;}}}}}printf("%d\n", dp[0]); //dp[0]表示0~L-1的最小删除字符串数目*///另一种方法，从前往后找 AC//dp[0] 表示0到0，dp[1]表示0~1,最后的的结果就是dp[L-1]for (i = 0; i <= L - 1;i++){//如果是从头往后，那第一个dp[0]的值最坏定为1if (0 == i){dp[i] = 1;}else{dp[i] = dp[i-1]+1;}//找匹配的字典单词for (j = 1; j <= W; j++) //开始遍历字典{len = strlength(dictionary[j]); //长度//挨个比较字符是否匹配//查看是否有字符串是匹配的，当然中间可能是有些字符是多余的那就要删掉//是的，从前往后的话，那比较单词就要从最后一个单词比较起了if (len <= (i+1) && (dictionary[j][len-1] == word[i])) //长度小于等于我们现在新增的，然后字典那个单词要一致{//这个比较的地方自己也是有点犹豫了pw = i; //从i开始一直到L-1pd = len-1;while (pw>=0){//找到匹配的单词，那字典就可以移一位if (dictionary[j][pd] == word[pw]){pd -= 1;}pw -= 1;if (pd == -1) //找到单词匹配{if (-1 == pw){dp[pw] = 0; //如果是正好前3个单词就是一个字典单词，那这个时候pw就=-1}dp[i] = min(dp[i], (dp[pw] + i - pw - len)); //i - pw -len表示 i-pw 表示移动了多长的字符串,因为从0开始的，然后匹配到len的字符，因为中间可能会有多的字符break;}}}}}printf("%d\n", dp[L-1]);return 0;
}

这篇关于POJ3267The Cow Lexicon(AC)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---