Problem Description现在有一些被简单压缩的字符串，例如:a[120]代表120个a。对于字符串acb[3]d[5]e相对于acbbbddddde
现在给你两个字符串cString, nString.一个是被压缩过的字符串,另一个没有被压缩。
求nString是否为cString的子串，如果是输出True，否则输出False.cString的长度clen的范围是0<clen<1000, nString的长度的nlen的范围是0<nlen<1000;cString只包含小写26个字母,[ ],数字(大于0小于10^9)。nString只包含小写26个字母。
Sample Input Sample Output//Accepted 2183 GNU C++ 0 ms 240KB 2891B
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N= 1100;
char a[N];
char b[N];
int cnta[N],cntb[N];
int main()
{
while(~scanf("%s%s",a,b))
{
int lena=strlen(a);
int lenb=strlen(b);
int l=0;
int num[15];
int top=0;
for(int i=0;i<lena;i++)
{
if(a[i]=='[') continue;
else if(a[i]>='0'&&a[i]<='9')
{
num[top++]=a[i]-'0';
}
else if(a[i]==']')
{
int sum=0;
for(int i=0;i<top;i++)
{
sum=sum*10+num[i];
}
top=0;
cnta[l-1]=sum;
}
else
{
a[l]=a[i];
cnta[l++]=1;
}
}
lena=l;
a[lena]=0;
l=1;
for(int i=1;i<lena;i++)
{
if(a[i]==a[l-1])
{
cnta[l-1]+=cnta[i];
continue;
}
else
{
a[l]=a[i];
cnta[l++]=cnta[i];
}
}
lena=l;
a[lena]=0;
l=1;
cntb[0]=1;
for(int i=1;i<lenb;i++)
{
if(b[i]==b[l-1])
{
cntb[l-1]++;
continue ;
}
else
{
b[l]=b[i];
cntb[l++]=1;
}
}
lenb=l;
b[lenb]=0;
bool flag;
for(int i=0;i<lena;i++)
{
int j;
flag=0;
l=0;
for(j=0;i+l<lena&&j<lenb;j++,l++)
{
if(a[i+l]==b[j])
{
if(j==0||j==lenb-1)
{
if(cnta[i+l]>=cntb[j])
{
if(j==lenb-1)flag=true;
continue;
}
else break;
}
else
{
if(cnta[i+l]==cntb[j])
continue;
else break;
}
}
else break;
}
if(j==lenb&&flag)
{
puts("True");
break;
}
}
if(!flag) puts("False");
}
return 0;
}
//Accepted 2183 GNU C++ 15 ms 11000KB 1996B
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6+1e3;
char t[N],b[N],a[N];
int cnt[N];
int next[N];
void getnext(char str[],int m,int next[])
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&str[i]!=str[j]) j=next[j];
next[++i]=++j;
}
}
bool KMP(char x[],char y[],int m,int n)
{
int i,j;
i=j=0;
while(i<n)
{
while(-1!=j&&y[i]!=x[j]) j=next[j];
i++;
j++;
if(j>=m) return true;
}
return false;
}
int main()
{
while(~scanf("%s%s",t,b))
{
int lent=strlen(t),lenb=strlen(b);
int l=0;
int top=0;
int num[15];
for(int i=0;i<lent;i++)
{
if(t[i]=='[') continue;
if(t[i]>='0'&&t[i]<='9')
{
num[top++]=t[i]-'0';
continue;
}
else if(t[i]==']')
{
int sum=0;
for(int i=0;i<top;i++)
{
sum=10*sum+num[i];
}
top=0;
cnt[l-1] = sum;
// printf("sum=%d\n",sum);
continue;
}
else
{
t[l]=t[i];
cnt[l++]=1;
}
}
lent=l;
t[lent]=0;
l=0;
for(int i=0;i<lent;i++)
{
int c=cnt[i];
if(c>lenb) c=lenb;
while(c--)
a[l++]=t[i];
}
int lena=l;
a[lena]=0;
getnext(b,lenb,next);
if(KMP(b,a,lenb,lena)) puts("True");
else puts("False");
}
return 0;
}
原文：http://blog.csdn.net/kalilili/article/details/44572735