EOJ201 Software Industry Revolution
Time Limit: 5000MS Memory Limit: 65536K
Total Submits: 34 Accepted: 12
Description
Making revolutions in the software industry is not an easy task. That’s why this problem is about something else. Stanescu has just invented a new super-cool way to develop software. It is similar to writing program code, but instead of writing it, you ask some else to do it. In such way, one could create great software, without even knowing what a Turing Machine is. As you can see, this is not just software industry revolution. Really, Stanescu does not care about the software industry at all. He just wants to make money.
In order to protect the money he is going to make, he needs to pick a special password for his bank account, satisfying the following requirements:
The password should not be too complex, so that Stanescu can remember it. The complexity of a password is the sum of the complexity of its characters and the complexity of a character is its position in the alphabet (for ’a’ it is 1, for ’b’ – 2, and so on). For example, the complexity of the string ”ala” is 1 + 12 + 1 = 14;
It should match a given pattern string (composed of lowercase Latin letters, ’?’ and ’*’, no longer than 1000 characters). ’?’ is matched by one arbitrary lowercase Latin letter, and ’*’ – by zero or more arbitrary lowercase Latin letters;
It should be a sub-string of given super-password string (composed of lowercase Latin letters, no longer than 10000).
You have to write a program that computes the complexity of simplest possible password.
Input
Several test cases are given at the input. Each of them consists of a single line containing the pattern and the super-password strings separated by a white space.
Output
For each test case, your program should print a single line with one integer – the complexity of the simplest possible password. If no password satisfies the given requirements, the program should print -1.
Sample Input
a?a alabala
a*c?a axcbaabcbax
Sample Output
4
9
Hint
For the first test case, aba is the simplest password
For the second one, abcba is simpler than axcba
***************************************************************
题目大意：先规定一个字符串的值为这个字符串中所有字母值的和，字母的值为该字母的ascii值减去a字母的ascii值+1，也就是 a的值是1，b的值是2.现在给定一个模式串和主串，模式串由小写字母、'?'、'*'组成，一个'?'匹配一个字母，一个'*'匹配任意多个字母（包括0个）。问，当模式串能成为主串的一个子串的时候，求这个模式串的最小值。若不能成为主串的子串就输出-1.
解题思路：这道题，对我着实有点小难，刚开始我是绝对没有思路的，然后，听了光神的话，原来对于这种有特殊符号的字符串的匹配问题可以先把模式串根据特殊符号分成很多个子模式串，然后一一找匹配，然后再根据特殊符号的要求来具体解题。对于这道题目，就先按照'?'和'*'把模式串分成多个子模式串，然后把每个模式串在能被主串匹配的地方记录下来，我们可以暴力一点：先枚举第一个子模式串被匹配的位置，然后根据第一个子模式串和第二个子模式串之间'?'和'*'的情况找第二个子模式串的位置并枚举，第三个子模式串的位置根据第二个来找，这样一直把所有位置都dfs一遍就可以了。但是，当子模式串能匹配的位置很多的时候，这个dfs是不明智的选择，直接超时。
因为我们其实只要求对于第一个子模式串定下来的位置，之后最后一个子模式串所在的位置的最前面的值。那么，我们就可以从后往前枚举第一个子模式串所在的位置，一旦当dfs到某个串的时候，这个串的位置之间已经找过了就不用找下去了。这个优化相当的巨大！直接300MS秒过此题登顶无压力！
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 100005
#define M 100005
#define inf 0x3f3f3f3f
using namespace std;
struct Node
{
int st,ed,flag;
Node(int a,int b,int c):st(a),ed(b),flag(c){}
};
char pat[N],str[M];//pat为模式串，str为主串
vector<Node>zpat[M];//zpat记录某个子模式串i能有的匹配位置
int sum[N],fail[M],lenpat,lenstr,ans;
int qmlast,zpatnum;//qmlast记录pat末尾有几个'?'，zpatnum记录有几个子模式串
int qmpre[M];//qmpre记录每个子模式串之前有几个'?'
bool smpre[M];//smpre记录每个子模式串前是否有'*'
//求主串中从a到b位置的字母和
int rsum(int a,int b)
{
if(a==0)return sum[b];
return sum[b]-sum[a-1];
}
//函数返回该子模式串是否能被匹配
int KMP(char *t,int *p,int n,int id)
{
for(int i=1;i<n;i++)
{
int k=p[i-1];
while(1)
{
if(t[i]==t[k+1])
{
p[i]=k+1;
break;
}
if(k==-1)break;
k=p[k];
}
}
int flag=0,j=-1;
for(int i=0;i<lenstr-qmlast;i++)
{
while(1)
{
if(str[i]==t[j+1])
{
j++;
if(j+1==n)
{
zpat[id].push_back(Node(i-n+1,i,0));
flag=1;
j=p[j];
}
break;
}
if(j==-1)break;
j=p[j];
}
}
return flag;
}
//返回整个模式串作为子串时之后一个字母在主串中的位置
//参数id表示第id个子模式串，lim表示第id个子模式串的在主串中的开头位置不能小于等于lim
int solve(int id,int lim)
{
if(id>=zpatnum)return lim;
lim+=qmpre[id];
int le=0,ri=zpat[id].size(),mid;
while(mid=(le+ri)/2,le<ri)
{
if(zpat[id][mid].st>lim)ri=mid;
else le=mid+1;
}
if(ri==zpat[id].size())return -1;
if((!smpre[id]&&zpat[id][ri].st!=lim+1))return -1;
for(int i=ri;i<zpat[id].size();i++)
{
if(zpat[id][i].flag)return -1;
zpat[id][i].flag=1;
int k=solve(id+1,zpat[id][i].ed);
if(~k)return k;
if(!smpre[id])break;
}
return -1;
}
void run(void)
{
ans=inf;
memset(fail,-1,sizeof(fail));
lenpat=strlen(pat);
lenstr=strlen(str);
sum[0]=str[0]-'a'+1;
for(int i=1;i<lenstr;i++)
sum[i]=sum[i-1]+str[i]-'a'+1;
qmlast=0;
for(lenpat--;lenpat>=0&&(pat[lenpat]=='*'||pat[lenpat]=='?');lenpat--)
qmlast+=(pat[lenpat]=='?');
if(lenpat<0)
{
if(qmlast==0)
ans=0;
else if(qmlast>lenstr)
ans=-1;
else
for(int i=qmlast-1;i<lenstr;i++)
ans=min(ans,rsum(i-qmlast+1,i));
return ;
}
zpatnum=0;lenpat++;
for(int i=0;i<lenpat;zpatnum++)
{
smpre[zpatnum]=false;
qmpre[zpatnum]=0;
zpat[zpatnum].clear();
while(pat[i]=='*'||pat[i]=='?')
{
if(pat[i]=='*')smpre[zpatnum]=true;
if(pat[i]=='?')qmpre[zpatnum]++;
i++;
}
int st=i;
int lenzpat=0;
while(i<lenpat&&pat[i]!='*'&&pat[i]!='?')
lenzpat++,i++;
if(KMP(pat+st,fail+st,lenzpat,zpatnum)==0)
return ;
}
for(int i=zpat[0].size()-1;i>=0;i--)
{
int st=zpat[0][i].st,ed=zpat[0][i].ed;
if(st<qmpre[0])continue;
ed=solve(1,ed);
if(ed==-1)continue;
ans=min(ans,rsum(st-qmpre[0],ed+qmlast));
}
}
int main()
{
while(scanf("%s",pat)!=EOF)
{
scanf("%s",str);
run();
printf("%d\n",ans==inf?-1:ans);
}
return 0;
}
