Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <algorithm>
- #include <math.h>
- #include <stdlib.h>
- #include <string>
- #include <string.h>
- #include <vector>
- #include <map>
- #include <valarray>
- #include <set>
- #include <limits.h>
- #include <ctime>
- #include <stack>
- #include <queue>
- #include <ctype.h>
- #include <complex>
- using namespace std;
- typedef complex<double> base;
- const double PI = acos(-1.0);
- int R[280000];
- base W[280000][2];
- int rev(int x,const int& l) {
- int sol = 0;
- for(int i=0;i<=l;i++) {
- sol <<= 1;
- sol |= (x&1);
- x >>= 1;
- }
- return sol;
- }
- void fft(vector<base>& a,const int& invert) {
- int n = a.size();
- for(int i=0;i<n;i++) {
- if(i<R[i]) {
- swap(a[i],a[R[i]]);
- }
- }
- for(int p=2;p<=n;(p<<=1)) {
- int wn = n/p;
- for(int i=0;i<n;i+=p) {
- int ind = 0;
- for(int j=0;j<(p>>1);j++) {
- base u = a[i+j], t = a[i+j+(p>>1)] * W[ind][invert];
- ind = ((ind+wn) & (n-1));
- a[i+j] = u + t;
- a[i+j+(p>>1)] = u - t;
- }
- }
- }
- if (invert)
- for(int i=0;i<n;i++)
- a[i] /= n;
- }
- char s[131172];
- int main() {
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- freopen("a2.in","r",stdin);
- freopen("a2.out","w",stdout);
- //int Time = clock();
- int n;
- scanf("%d\n",&n);
- gets(s);
- vector<int> a(n),b(n);
- for(int i=0;i<n;i++) {
- switch (s[n-i-1]) {
- case ('A'):
- a[i] = 0;
- break;
- case ('C'):
- a[i] = 1;
- break;
- case ('G'):
- a[i] = 2;
- break;
- default:
- a[i] = 3;
- break;
- }
- }
- gets(s);
- for(int i=0;i<n;i++) {
- switch (s[n-i-1]) {
- case ('A'):
- b[i] = 0;
- break;
- case ('C'):
- b[i] = 1;
- break;
- case ('G'):
- b[i] = 2;
- break;
- default:
- b[i] = 3;
- break;
- }
- }
- int o=0;
- while((1 << o)<n) o++;
- vector<int> m(n,0);
- for(int i=0;i<(n<<1);i++) {
- R[i] = rev (i,o);
- }
- W[0][0] = 1;
- W[0][1] = 1;
- double ang = 2*PI/(n<<1);
- base w(cos(ang),sin(ang));
- W[1][0] = w;
- for(int i=2;i<=(n<<1);i++) {
- W[i][0] = W[i-1][0] * w;
- }
- ang = -2*PI/(n<<1);
- base wn(cos(ang),sin(ang));
- W[1][1] = wn;
- for(int i=2;i<=(n<<1);i++) {
- W[i][1] = W[i-1][1] * wn;
- }
- for(int p=0;p<4;p++) {
- vector<base> x(n<<1,0),y(n<<1,0);
- for(int i=0;i<n;i++) {
- x[n-i-1] = (a[i] == p) ? 1 : 0;
- y[i] = (b[i] == p) ? 1 : 0;
- y[i+n] = y[i];
- }
- fft(x,0);
- fft(y,0);
- for(int i=0;i<(n<<1);i++) {
- x[i] *= y[i];
- }
- fft(x,1);
- for(int i = 0; i<n; i++) {
- m[i] += int(x[n-1+i].real()+0.5);
- }
- }
- int ps = 0;
- for(int i=1;i<n;i++) {
- if(m[i] > m[ps]) ps = i;
- }
- printf("%d %d\n",m[ps],ps);
- //printf("%.3f",float(clock()-Time)/1000);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement