|
|
please give some test data!! Edited by author 20.10.2007 08:04 Mind mod, I had 10^7+7 and it was failing abc cba 6 aba bab 2 abcabc cba 5 abcbaabdca abcada 1 abcabbaca abcabbc 1 thnx a lot for your tests What's this test?? My code: #include <string> #include <algorithm> #include <iostream> #define N 2222 #define MOD 1000000007ll using namespace std; long long f[N][N],d[N][N]; int n,m; string s1,s2; void init(){ getline(cin,s1); getline(cin,s2); n=s1.length(),m=s2.length(); } int main(){ init(); for (int i=0;i<=n;i++) d[i][0]=i; for (int i=0;i<=m;i++) d[0][i]=i; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1; else d[i][j]=min(d[i-1][j],d[i][j-1])+1; for (int i=0;i<=n;i++) f[i][0]=1; for (int i=0;i<=m;i++) f[0][i]=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ if (d[i][j]==i || d[i][j]==j) f[i][j]=1; else{ if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]; else f[i][j]=f[i-1][j]+f[i][j-1]; } f[i][j]%=MOD; } cout<<f[n][m]<<endl; } You can try this: dcfc dbf Answer:2 LOL, replying after 7 years. Could someone provide tests for me? Thank you Is this a problem for counting the number of shortest common superstrings ??? Please help me with test case 16 Python: 7028591 The same C++: 7028621 Please increase memory limit or disable python. Thanks Those who have got AC please provide with some test cases. My program fails at test 9. Dont know why. Edited by author 22.09.2012 23:23 see the second sample on your site. the answer is 2. Any suggestions on improvement of the algorithm i use? Is my approach wrong or can be fine with some tweaking? Ravi Kiran. If in your current state s1[i]==s2[j], you should not assume states i+1,j and i,j+1. Only i+1,j+1. Thanks a lot everyone. I got accepted with the change you suggested. pls Give some test data Edited by author 18.10.2007 03:47 |
|
|