热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2017PresummerTrainingISearchingandStrings

B.单词替换(KMP+Lazy标记)SampleInputSampleOutputCode:1#include2usingnamespacestd;3s

B. 单词替换(KMP + Lazy标记)

技术分享

Sample Input

3
aaa
a
b
aaa
aa
b
ababa
aba
cd

Sample Output

bbb
ba
cdba

 技术分享

Code:

技术分享技术分享
 1 #include 
 2 using namespace std;
 3 static const int MAXN = 5e6 + 10;
 4 bool vis[MAXN];
 5 char text[MAXN] = {\0};
 6 char pattern[MAXN] = {\0};
 7 char fuck[MAXN];
 8 int nxt[MAXN];
 9 int ans;
10 void GetNext(char* s , int len)
11 {
12     int j;
13     j = nxt[0] = -1;
14     for(int i = 1 ; i i)
15     {
16         while(j != -1 && s[i] != s[j + 1])
17             j = nxt[j];
18         if(s[i] == s[j + 1])
19             ++j;
20         nxt[i] = j;
21     }
22 }
23 void Kmp()
24 {
25     int n = strlen(text) , m = strlen(pattern);
26     GetNext(pattern , m);
27     int j = -1;
28     for(int i = 0 ; i i)
29     {
30         while(j != -1 && text[i] != pattern[j + 1])
31             j = nxt[j];
32         if(text[i] == pattern[j + 1])
33             ++j;
34         if(j == m - 1)
35         {
36             vis[i - m + 1] = 1;
37         }
38     }
39 }
40 int main()
41 {
42     int t;
43     scanf("%d" , &t);
44     while(t--)
45     {
46         ans = 0;
47         memset(nxt , 0 , sizeof(nxt));
48         memset(vis , 0 , sizeof(vis));
49         memset(pattern , \0 , sizeof(pattern));
50         memset(text , \0 , sizeof(text));
51         scanf(" %s" , text);
52         scanf(" %s" , pattern);
53         scanf(" %s" , fuck);
54         Kmp();
55         int n = strlen(text) , m = strlen(pattern);
56         for(int i = 0 ; i < n ; )
57         {
58             if(vis[i])
59             {
60                 printf("%s" , fuck);
61                 i += m;
62             }
63             else
64             {
65                 printf("%c" , text[i++]);
66             }
67         }
68 
69         printf("\n");
70     }
71 }
View Code

2017 Pre-summer Training I - Searching and Strings


推荐阅读
author-avatar
George
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有