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;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
