Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <cctype>
- #include <cstdlib>
- #include <fstream>
- #include <vector>
- #include <string>
- #include <sstream>
- #include <stack>
- #include <queue>
- #include <map>
- #include <set>
- #include <list>
- #include <bitset>
- #include <numeric>
- #include <algorithm>
- #include <functional>
- using namespace std;
- #define PI 2*acos(0.0)
- #define FOR(i,n) for(int i = 0;i<n;++i)
- #define setbit(a,b) a|=(1<<b)
- #define S1(a) scanf("%d",&a)
- #define S2(a,b) scanf("%d %d",&a,&b)
- #define S3(a,b,c) scanf("%d %d %d",&a,&b,&c)
- #define C1(a) __builtin_popcount(a)
- #define gcd(a,b) __gcd(a,b)
- #define ALL(a) (a.begin(),a.end())
- typedef long long LL;
- typedef vector<int> vi;
- const int INF = (1LL<<31)-1;
- char inpt[1000005];
- map< string,int > mp;
- int main(){
- int n;
- while( S1(n)==1 )
- {
- mp.clear();
- scanf("%s",inpt);
- string subStr = "";
- int mx = 0,r = 0;
- //i am not using strlen because it takes time :( inpt[i] works fine.
- for(int i = 0;inpt[i];++i)
- {
- subStr += inpt[i];
- //other than making substr every time i can just erase the first character.
- // say after "abc" when d comes i will make it "abcd" and then remove a, thus it will become "bcd".
- if( i >= n )
- {
- subStr.erase(subStr.begin(),subStr.begin()+1);
- }
- //accesing map consumes log(n) time. so i will store the map value in a variable and later i will only use this variable.
- int cur = mp[ subStr ]++;
- ++cur;
- if( mx < cur )
- {
- mx = cur;
- //if we copy the result string every time it takes a bit time also :P
- //i will only kow the first index from where to print the result.
- r = i-n+1;
- }
- }
- for(int i = r;i<r+n;++i)printf("%c",inpt[i]);
- puts("");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment