計ニンニク客15500阿里天池の新しい任務(簡単)の題解
4764 ワード
に言及
アリの「天池」コンテストプラットフォームは最近、与えられた一連のDNA塩基配列tについて、ルールに基づいて生成された別のDNA塩基配列sに何回現れたかを判断する新しい挑戦任務を発表した.
まず、シーケンスwを定義する.
wi={b,(wi−1+a)modn,i=0i>0
次に、長さnのDNA塩基配列s(以下、0から始まる)を定義する.
si=⎧⎩⎨⎪⎪⎪⎪⎪⎪A,T,G,C,(L≤wi≤R)∧(wi mod 2=0)(L≤wi≤R)∧(wi mod 2=1)((wiR))∧(wi mod 2=0)((wiR))∧(wi mod 2=1)
ここで∧は「かつ」関係を表し、∨は「または」関係を表し、a mod bはaをbで割った余りを表す.
次に、別のDNA塩基配列tが与えられ、sを生成するパラメータn,a,b,L,Rが与えられ、tがsに何回現れたかを求める.
構想
式に従ってsシーケンスを生成し、KMPを行う
コード#コード#
アリの「天池」コンテストプラットフォームは最近、与えられた一連のDNA塩基配列tについて、ルールに基づいて生成された別のDNA塩基配列sに何回現れたかを判断する新しい挑戦任務を発表した.
まず、シーケンスwを定義する.
wi={b,(wi−1+a)modn,i=0i>0
次に、長さnのDNA塩基配列s(以下、0から始まる)を定義する.
si=⎧⎩⎨⎪⎪⎪⎪⎪⎪A,T,G,C,(L≤wi≤R)∧(wi mod 2=0)(L≤wi≤R)∧(wi mod 2=1)((wi
ここで∧は「かつ」関係を表し、∨は「または」関係を表し、a mod bはaをbで割った余りを表す.
次に、別のDNA塩基配列tが与えられ、sを生成するパラメータn,a,b,L,Rが与えられ、tがsに何回現れたかを求める.
構想
式に従ってsシーケンスを生成し、KMPを行う
コード#コード#
#include 1)
{
while(tt>0&&t[i-1]!=t[tt-1])
tt=next[tt];
tt++;
i++;
if(t[i-1]==t[tt-1])
next[i]=next[tt];
else next[i]=tt;
}
while(tt>0&&t[i-1]!=t[tt-1])
tt=next[tt];
tt++;
i++;
next[i]=tt;
}
int kmp()
{
int i=0,j=1,n=0;
int lt,ls;
lt=strlen(t);
ls=strlen(s);
while(lt+1-j<=ls-i)
{
if(s[i]==t[j-1])
{
i++;
j++;
if(j==lt+1)
{
n++;
j=next[j];
}
}
else
{
j=next[j];
if(j==0)
{
i++;
j++;
}
}
}
return n;
}
int main()
{
scanf("%d%d%d%d%d",&n,&a,&b,&L,&R);
scanf("%s",t);
for(int i=0;iif(i==0)
w=b;
else w=(w+a)%n;
if(w>=L&&w<=R&&w%2==0)
s[i]='A';
else if(w>=L&&w<=R&&w%2==1)
s[i]='T';
else if(w%2==0)
s[i]='G';
else s[i]='C';
}
//printf("%s
",s);
//printf("%s
",t);
l=strlen(t);
buildnext();
printf("%d
",kmp());
return 0;
}