首页 > 代码库 > 【NOIP2015】子串

【NOIP2015】子串

2024-08-14 05:40:13   223人阅读

题意：有AB两个字符串，用A中连续的K串匹配B全串，问不同的方案总数

n<=1000,m<=200,k<=m

思路：设dp[k,i,j]为用k串 A中前i个字符匹配B中前j个字符的方案总数

         首先dp[k,i,j]=0 (a[i]<>b[j])

         然后就是考虑dp[k,i,j]能否从dp[k,i-1,j-1]即前一个连续转移来 dp[k,i,j]=dp[k,i,j]+dp[k,i-1,j-1]

         还有就是另起一串 dp[k,i,j]=dp[k-1,1,j-1]+dp[k-1,2,j-1]+...+dp[k-1,i-1,j-1]

         转移用前缀和优化，空间用滚动数组优化

       技术分享

暴力

 1 const mo=1000000007; 2 var dp:array[0..50,0..500,0..500]of longint; 3     a,b:ansistring; 4     n,m,k1,i,j,k,x,ans:longint; 5  6 begin 7  //assign(input,‘1.in‘); reset(input); 8  //assign(output,‘1.out‘); rewrite(output); 9  readln(n,m,k1);10  readln(a);11  readln(b);12  dp[0,0,0]:=1;13  for i:=1 to n do14   if a[i]=b[1] then dp[1,i,1]:=1;15  for i:=1 to k1 do16   for j:=1 to n do17    for k:=1 to m do18    begin19     if a[j]<>b[k] then continue;20     if a[j-1]<>b[k-1] then21      for x:=1 to j-1 do dp[i,j,k]:=(dp[i,j,k]+dp[i-1,x,k-1]) mod mo22       else23       begin24        for x:=1 to j-1 do dp[i,j,k]:=(dp[i,j,k]+dp[i-1,x,k-1]) mod mo;25        dp[i,j,k]:=(dp[i,j,k]+dp[i,j-1,k-1]) mod mo;26       end;27    end;28  for i:=1 to n do ans:=(ans+dp[k1,i,m]) mod mo;29  writeln(ans);30 // close(input);31 // close(output);32 end.

 

加了优化

 1 const mo=1000000007; 2 var dp,f:array[0..1,0..1000,0..200]of longint; 3     a,b:ansistring; 4     n,m,k1,i,v,j,k,ans:longint; 5  6 begin 7  //assign(input,‘1.in‘); reset(input); 8  //assign(output,‘1.out‘); rewrite(output); 9  readln(n,m,k1);10  readln(a);11  readln(b);12  dp[0,0,0]:=1;13  for i:=0 to n do f[0,i,0]:=1;14  for i:=1 to k1 do15  begin16   v:=1-v;17   fillchar(f[v],sizeof(f[v]),0);18   fillchar(dp[v],sizeof(dp[v]),0);19   for j:=1 to n do20    for k:=1 to m do21    begin22     if a[j]=b[k] then23     begin24      dp[v,j,k]:=f[1-v,j-1,k-1];25      if a[j-1]=b[k-1] then dp[v,j,k]:=(dp[v,j,k]+dp[v,j-1,k-1]) mod mo;26     end;27     f[v,j,k]:=(f[v,j-1,k]+dp[v,j,k]) mod mo;28    end;29  end;30  for i:=1 to n do ans:=(ans+dp[v,i,m]) mod mo;31  writeln(ans);32  //close(input);33  //close(output);34 end.

 

【NOIP2015】子串


联系
我们