URAL 1732 . Ministry of Truth KMP
来源：程序员人生 发布时间：2014-09-11 15:42:20 阅读次数：2693次
题目来源：URAL 1732 . Ministry of Truth
题意：把第一个字符串处理一下 变成第二个 不要的字符改成下划线 空格不能改
思路：对第二个字符串单词分割 得到每一个单词后从第一个字符串中匹配 匹配成功 记录当前匹配的位置 然后下一个单词从x+2处在匹配 知道所有的单词都被匹配到
鄙视自己没想清楚写了半天 最后发现题目意思都错了
改了很多 最后代码和原来的完全不一样了 以后想清楚在写
样例
abcd和ab d输出ab_c
abcx abcxx abcxx和abc abc abc x 输出abc_ abc__ abc_x
hhahaphapphappyhappyhh和hap happ hh输出___hap____happ______hh
lossiblossible和lossible输出______lossible
a b c和a输出a _ _
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100010;
char a[maxn], b[maxn], c[maxn];
int f[maxn];
void get_fail(char *p)
{
f[0] = f[1] = 0;
int n = strlen(p);
for(int i = 1; i < n; i++)
{
int j = f[i];
while(j && p[i] != p[j])
j = f[j];
if(p[i] == p[j])
f[i+1] = j+1;
else
f[i+1] = 0;
}
}
int find(char* a, char* b, int s)
{
int j = 0;
int m = strlen(b);
int i;
for(i = s; a[i] != 0; i++)
{
while(j && a[i] != b[j])
j = f[j];
if(a[i] == b[j])
j++;
if(j == m)
{
int k = s-1;
if(k < 0)
k = 0;
for(; k <= i-m; k++)
{
if(a[k] != ' ')
a[k] = '_';
}
//for(int k = i+1; a[k] != ' ' && a[k] != 0; k++)
//a[k] = '_';
return i;
}
}
return -1;
}
int main()
{
while(gets(a))
{
int n = strlen(a);
gets(b);
char* p = strtok(b, " ");
get_fail(p);
int i = 0;
int flag = 0;
while(p && i < n)
{
int x = find(a, p, i);
if(x == -1)
{
flag = 1;
break;
}
i = x+2;
p = strtok(NULL, " ");
if(p)
get_fail(p);
}
i--;
for( ; i < n; i++)
if(a[i] != ' ')
a[i] = '_';
if(flag)
puts("I HAVE FAILED!!!");
else
puts(a);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
