字符串
HDU 2087 剪花布条
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Sample Input
abcde a3
aaaaaa aa
Sample Output
0
3
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char a[1000100],b[1000100];
int p[1000100];
int main()
{
while(scanf("%s",a+1)&& a[1] != '#'&&scanf("%s",b+1)){
memset(p,0,sizeof(p));//a为字符串，b为模式串
int la=strlen(a+1),lb=strlen(b+1);
int count=0,j=0;
p[1]=0;
//先处理出p数组，无非是b和自己匹配，与b和a匹配一样，故代码差不多
for(int i=2;i<=lb;i++)
{
while(j>0 && b[i]!=b[j+1]) j=p[j];//往前翻记录了有相同前缀的j
if(b[i]==b[j+1]) j++;//i匹配成功了，i继续往后
p[i]=j;
}
j=0;
//两个字符串匹配
for(int i=1;i<=la;i++)
{
while(j>0 && a[i]!=b[j+1]) j=p[j];
if(a[i]==b[j+1]) j++;
if(j==lb)
count++,j=0;
}
printf("%d\n",count);
}
return 0;
}
HDU 1686 Oulipo
典型的KMP板子题（同 HDU 1711 Number Sequence）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char a[1000100],b[1000100];
int p[1000100];
int main()
{ int t;
scanf("%d",&t);
while(t--){
scanf("%s%s",b+1,a+1);
memset(p,0,sizeof(p));//a为字符串，b为模式串
int la=strlen(a+1),lb=strlen(b+1);
int count=0,j=0;
p[1]=0;
//先处理出p数组，无非是b和自己匹配，与b和a匹配一样，故代码差不多
for(int i=2;i<=lb;i++)
{
while(j>0 && b[i]!=b[j+1]) j=p[j];//往前翻记录了有相同前缀的j
if(b[i]==b[j+1]) j++;//i匹配成功了，i继续往后
p[i]=j;
}
j=0;
//两个字符串匹配
for(int i=1;i<=la;i++)
{
while(j>0 && a[i]!=b[j+1]) j=p[j];
if(a[i]==b[j+1]) j++;
if(j==lb)
count++,j=p[j]; //从下一个模式串
}
printf("%d\n",count);
}
return 0;
}
HDU 1251 前缀统计
方法一：用string和map解决
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<string.h>
using namespace std;
map<string,int>pre;
int main(){
char a[12];
while(gets(a)){
if(a[0]=='\0')//或者写成==NULL
break;
string str=a;//用字符串来存储字符数组a
for(int i=1;i<=str.size();i++){
string s=str.substr(0,i);//在string中使用
pre[s]++;
}
/*
string s="";
for(int i=0;a[i];i++)
{
s+=a[i];//这样写也可以
pre[s]++;
}
*/
}
while(gets(a))
{
string s=a;
printf("%d\n",pre[s]);
}
return 0;
}
方法二：采用二维数组用字典树来解决
#include <iostream>
#include <stdio.h>
using namespace std;
int trie[1000010][26]; //数组形式定义字典树，值存储的是下一个字符的位置
int num[1000010]={0}; //附加值，以某一字符串为前缀的单词的数量
int pos = 1;
void Insert(char word[]) //在字典树中插入某个单词
{
int i;
int c = 0;
for(i=0;word[i];i++){
int n = word[i]-'a';
if(trie[c][n]==0) //如果对应字符还没有值
trie[c][n] = pos++;
c = trie[c][n];
num[c]++;
}
}
int Find(char word[]) //返回以某个字符串为前缀的单词的数量
{
int i;
int c = 0;
for(i=0;word[i];i++){
int n = word[i]-'a';
if(trie[c][n]==0)
return 0;
c = trie[c][n];
}
return num[c];
}
int main()
{
char word[11];
while(gets(word)){
if(word[0]==NULL) //空行。gets读入的回车符会自动转换为NULL。
break;
Insert(word);
}
while(gets(word))
printf("%d\n",Find(word));
return 0;
}
/* HDU1251 与前缀统计差不多，注意格式
banana
band
bee
absolute
acm
ba
b
band
abc
*/
POJ 2503 Babelfish
本题主要考察的是字符串的输入，题目是要通过词义检索单词。
方法一：用map<string,string>进行查找
#include <iostream>
#include <string>
#include <map>
#include<stdio.h>
using namespace std;
map <string,string>mp;
int main ()
{
char ch[30],str1[15],str2[15];
while (gets(ch))
{
if (ch[0]==NULL)
break;
sscanf(ch,"%s%s",str1,str2);
mp[str2]=str1;
}
while (gets(ch))
{
map<string,string>::iterator it;
it=mp.find(ch);//查找
if (it!=mp.end())
cout<<(*it).second<<endl;
else
printf("eh\n");
}
return 0;
}
方法二：通过对字符串排序二分查找答案
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
char s1[20],s2[20];
} a[100005];
int cmp(node a,node b)
{
return strcmp(a.s2,b.s2)<0;
// 若字符串1>字符串2 则返回1，
//字符串1<字符串2 则返回 -1,相等返回0。
}
int main()
{
int i,j,low,mid,high,flag=1,len=0;
char s[50];
while(gets(s))
{
//当是空行时，字符串的长度是零；或者字符串第一位是'\0'
//if(s[0]=='\0')
if(strlen(s)==0)
break;
//sscanf可以从s中读取两个字符串
sscanf(s,"%s%s",a[len].s1,a[len].s2);
len++;
}
sort(a,a+len,cmp);//按字典序排列所以字符串
//二分查找字符串
while(gets(s))
{
low=0;
high=len-1;
flag=1;
while(low<=high)
{
int mid =(low+high)/2;
if(strcmp(s,a[mid].s2)==0)
{
printf("%s\n",a[mid].s1);
flag = 0;
break;
}
else if(strcmp(s,a[mid].s2)>0)
low=mid+1;
else
high=mid-1;
}
if(flag==1)
printf("eh\n");
}
return 0;
}
CFGym 101466E Text Editor
题目链接: link.
题意：已知A串，B串，和整数k，求B的最长前缀，此前缀在A串中出现的次数大于等于k次
这里很容易想到二分，但一个一个去枚举判断答案（如下）会超出时间
bool check(char s[],char t[],int mid,int k){
str2=s;
str1="";
for(int i=0;i<mid;i++)
str1=str1+t[i];
for(int i=0;i<str2.size()-mid+1;i++){
str=str2.substr(i,mid);
if(str==str1)
mp[str1]++;
if(mp[str1]>=k){
mp.clear();
return 1;
}
}
mp.clear();
return 0;
}
因此我们联想到KMP算法，代码如下：
#include<stdio.h>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
string str,str1,str2;
char s[100005];
char t[100005];
int k,l,r,mid;
map<string,int>mp;//map映射
bool check(int mid,int k){
int p[100005]={0};
memset(p,0,sizeof(p));//a为字符串，b为模式串
int la=strlen(s+1),lb=mid;
int count=0,j=0;
p[1]=0;
//先处理出p数组，无非是b和自己匹配，与b和a匹配一样，故代码差不多
for(int i=2;i<=lb;i++)
{
while(j>0 && t[i]!=t[j+1]) j=p[j];//往前翻记录了有相同前缀的j
if(t[i]==t[j+1]) j++;//i匹配成功了，i继续往后
p[i]=j;
}
j=0;
//两个字符串匹配
for(int i=1;i<=la;i++)
{
while(j>0 && s[i]!=t[j+1]) j=p[j];
if(s[i]==t[j+1]) j++;
if(j==lb)
count++,j=p[j]; //从下一个模式串
}
// printf("la %d lb %d\n",la,lb);
// printf("%d\n",count);
if(count>=k)
return 1;
else
return 0;
}
int main(){
gets(s+1);
gets(t+1);
scanf("%d",&k);
l=0,r=strlen(t+1);
bool flag=0;
while(l<r){
mid=(l+r+1)/2;
if(check(mid,k)){
flag=1;
l=mid;
}
else
r=mid-1;
}
if(flag==1){
for(int i=1;i<=l;i++)
printf("%c",t[i]);
}
else
printf("IMPOSSIBLE\n");
return 0;
}
UVA 11475 Extend to Palindrome
题意：求字符串末尾最少添加多少个字符可以把他变成回文串，输出这个回文串，很明显只要用KMP[判断一下反串和字符串最多能匹配到哪个位置，结尾加上反串这个位置之后的所有字符就可以了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char a[1000100],b[1000100];
int p[1000100];
int main()
{
while(gets(a+1)){
for(int i=1;i<=strlen(a+1);i++)
b[strlen(a+1)-i+1]=a[i];
memset(p,0,sizeof(p));//a为字符串，b为模式串
int la=strlen(a+1),lb=la;
int count=0,j=0;
p[1]=0;
//先处理出p数组，无非是b和自己匹配，与b和a匹配一样，故代码差不多
for(int i=2;i<=lb;i++)
{
while(j>0 && b[i]!=b[j+1]) j=p[j];//往前翻记录了有相同前缀的j
if(b[i]==b[j+1]) j++;//i匹配成功了，i继续往后
p[i]=j;
}
j=0;
//两个字符串匹配
for(int i=1;i<=la;i++)
{
while(j>0 && a[i]!=b[j+1]) j=p[j];
if(a[i]==b[j+1]) j++;//j为最多可以匹配到的位置
// if(j==lb)
// count++,j=p[j]; //从下一个模式串
}
for(int i=1;i<=la;i++)
printf("%c",a[i]);
for(int i=j+1;i<=la;i++)
printf("%c",b[i]);
printf("\n");
}
return 0;
}