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
***************************************************************
題目大意：先規(guī)定一個(gè)字符串的值為這個(gè)字符串中所有字母值的和，字母的值為該字母的ascii值減去a字母的ascii值+1，也就是 a的值是1，b的值是2.現(xiàn)在給定一個(gè)模式串和主串，模式串由小寫字母、'?'、'*'組成，一個(gè)'?'匹配一個(gè)字母，一個(gè)'*'匹配任意多個(gè)字母（包括0個(gè)）。問，當(dāng)模式串能成為主串的一個(gè)子串的時(shí)候，求這個(gè)模式串的最小值。若不能成為主串的子串就輸出-1.
解題思路：這道題，對我著實(shí)有點(diǎn)小難，剛開始我是絕對沒有思路的，然后，聽了光神的話，原來對于這種有特殊符號的字符串的匹配問題可以先把模式串根據(jù)特殊符號分成很多個(gè)子模式串，然后一一找匹配，然后再根據(jù)特殊符號的要求來具體解題。對于這道題目，就先按照'?'和'*'把模式串分成多個(gè)子模式串，然后把每個(gè)模式串在能被主串匹配的地方記錄下來，我們可以暴力一點(diǎn)：先枚舉第一個(gè)子模式串被匹配的位置，然后根據(jù)第一個(gè)子模式串和第二個(gè)子模式串之間'?'和'*'的情況找第二個(gè)子模式串的位置并枚舉，第三個(gè)子模式串的位置根據(jù)第二個(gè)來找，這樣一直把所有位置都dfs一遍就可以了。但是，當(dāng)子模式串能匹配的位置很多的時(shí)候，這個(gè)dfs是不明智的選擇，直接超時(shí)。
因?yàn)槲覀兤鋵?shí)只要求對于第一個(gè)子模式串定下來的位置，之后最后一個(gè)子模式串所在的位置的最前面的值。那么，我們就可以從后往前枚舉第一個(gè)子模式串所在的位置，一旦當(dāng)dfs到某個(gè)串的時(shí)候，這個(gè)串的位置之間已經(jīng)找過了就不用找下去了。這個(gè)優(yōu)化相當(dāng)?shù)木薮螅≈苯?00MS秒過此題登頂無壓力！
#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記錄某個(gè)子模式串i能有的匹配位置
int sum[N],fail[M],lenpat,lenstr,ans;
int qmlast,zpatnum;//qmlast記錄pat末尾有幾個(gè)'?'，zpatnum記錄有幾個(gè)子模式串
int qmpre[M];//qmpre記錄每個(gè)子模式串之前有幾個(gè)'?'
bool smpre[M];//smpre記錄每個(gè)子模式串前是否有'*'
//求主串中從a到b位置的字母和
int rsum(int a,int b)
{
if(a==0)return sum[b];
return sum[b]-sum[a-1];
}
//函數(shù)返回該子模式串是否能被匹配
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;
}
//返回整個(gè)模式串作為子串時(shí)之后一個(gè)字母在主串中的位置
//參數(shù)id表示第id個(gè)子模式串，lim表示第id個(gè)子模式串的在主串中的開頭位置不能小于等于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;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
