URAL 1732 . Ministry of Truth KMP
來源：程序員人生 發布時間：2014-09-11 15:42:20 閱讀次數：2823次
題目來源：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
