题目:http://codeforces.com/contest/1200/problem/E

Compress Words
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Amugae has a sentence consisting of nn words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.

Input

The first line contains an integer nn (1≤n≤1051≤n≤105), the number of the words in Amugae's sentence.

The second line contains nn words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed 106106.

Output

In the only line output the compressed word after the merging process ends as described in the problem.

Examples
input

Copy
5
I want to order pizza
output

Copy
Iwantorderpizza
input

Copy
5
sample please ease in out
output

Copy
sampleaseinout

题意:

给你n个字符串,你需要按顺序连接这些字符串,如果当前的字符串的前缀和上一个字符串的后缀相同,则连接时要去掉当前字符串的前缀

思路:

一开始暴力,果断TLE,然后用kmp,还是TLE,改了几十次后发现是每次调用kmp和getnex时都调用用了strlen,增加了复杂度,去掉之后就AC了
为什么用kmp呢?因为kmp可以在文本串中找到模板串匹配的部分,现在要当前字符串的前缀匹配上一个字符串的后缀,我们就从上一个字符串的长度-当前字符串的长度的位置开始找,
因为一个字符串的前缀最长是他本身,所以当前字符串的前缀最多能匹配到这个位置(再往前当前字符串的长度就不够了),然后用kmp匹配,然后返回一个当前字符串的前缀与上一个字符串的后缀不匹配的位置(就是return j,j是当前字符串匹配的位置,如果t[i]==p[j]则j++,所以返回时j会指向不匹配的位置)

注意:

如果调用太多次strlen会TLE!!!

 #include<bits/stdc++.h>
using namespace std;
const int amn=1e6+;
char ans[amn],in[amn];
int n,nex[amn],len,tp;
void getnex(char in[]){ ///不要在这调用strlen!!!,用已有的就好了,不然会T到自闭!!!
nex[]=nex[]=;
for(int i=;i<len;i++){
int j=nex[i];
while(j&&in[i]!=in[j])j=nex[j];
nex[i+]=in[i]==in[j]?j+:;
}
}
int kmp(char t[],char p[],int pos){ ///不要在这调用strlen!!!,用已有的就好了,不然会T到自闭!!!
getnex(in);
int j=;
for(int i=pos;i<tp;i++){
while(j&&p[j]!=t[i])j=nex[j];
if(p[j]==t[i])j++;
}
return j;
}
int main(){
ios::sync_with_stdio();
cin>>n;
cin>>ans;
int pos;
tp=strlen(ans); ///注意,如果调用太多次strlen会TLE!!!
for(int i=;i<=n;i++){
cin>>in;
len=strlen(in);
pos=tp-len; ///上一个字符串的长度-当前字符串的长度,因为一个字符串的前缀最长是他本身,他最多只能匹配到这个位置
for(int j=kmp(ans,in,pos);j<len;j++)
ans[tp++]=in[j];
}
for(int i=;i<tp;i++)
printf("%c",ans[i]);
printf("\n");
}
/**
给你n个字符串,你需要按顺序连接这些字符串,如果当前的字符串的前缀和上一个字符串的后缀相同,则连接时要去掉当前字符串的前缀
一开始暴力,果断TLE,然后用kmp,还是TLE,改了几十次后发现是每次调用kmp和getnex时都调用用了strlen,增加了复杂度,去掉之后就AC了
为什么用kmp呢?因为kmp可以在文本串中找到模板串匹配的部分,现在要当前字符串的前缀匹配上一个字符串的后缀,我们就从上一个字符串的长度-当前字符串的长度的位置开始找,
因为一个字符串的前缀最长是他本身,所以当前字符串的前缀最多能匹配到这个位置(再往前当前字符串的长度就不够了),然后用kmp匹配,然后返回一个当前字符串的前缀与上一个字符串的后缀不匹配的位置(就是return j,j是当前字符串匹配的位置,如果t[i]==p[j]则j++,所以返回时j会指向不匹配的位置)
然后从这个位置开始把当前字符串后面的字符都加到上一个字符串后面,知道输入完毕,最后输出ans就行了
注意:如果调用太多次strlen会TLE!!!
**/

最新文章

  1. Myeclipse反编译插件的安装
  2. 洛谷U4859matrix[单调栈]
  3. 中国移动测试大会 PPT 和视频
  4. js正则验证邮箱、手机号、年龄
  5. 51nod1122 机器人走方格 V4
  6. jooml二次开发---添加文章组件
  7. Tomacat服务器的安装和配置
  8. 在octopress中gist tab不能正确的插入gist代码
  9. Java中的编码格式
  10. Shell 学习笔记之变量
  11. Struts2拦截器记录系统操作日志
  12. freemarker入门实例
  13. 剑指Offer-求1+2+3+...+n
  14. 基于ARM_contexA9 led驱动编程
  15. HDU - 1035
  16. 关于python类变量和实例变量
  17. 二层协议--LLDP协议总结
  18. Shell - 简明Shell入门08 - 函数(Function)
  19. Mac svn使用学习-1-简介
  20. Odoo8出现Internal Server Error的解决办法之一

热门文章

  1. 张益肇:AI 医疗,微软有哪些布局?
  2. The difference between applicationContext.xml in Spring and xxx-servlet.xml in SpringMVC
  3. 在 React Native 中使用 moment.js 無法載入語系檔案
  4. 初学Qt——QTableView+QSqlqueryModel
  5. 达拉草201771010105《面向对象程序设计(java)》第十四周学习总结
  6. pip安装psycopg2失败解决
  7. 重置gitlab管理员密码
  8. Git 相关问题分享,git reset与git revert的区别?
  9. C与ARM汇编结合实现mini2440串口uart简单程序
  10. a标签嵌套href默认行为与子元素click事件存在影响