Guest User

Untitled

a guest
Dec 17th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cctype>
  6. #include <cstdlib>
  7. #include <fstream>
  8. #include <vector>
  9. #include <string>
  10. #include <sstream>
  11. #include <stack>
  12. #include <queue>
  13. #include <map>
  14. #include <set>
  15. #include <list>
  16. #include <bitset>
  17. #include <numeric>
  18. #include <algorithm>
  19. #include <functional>
  20. using namespace std;
  21.  
  22. #define PI 2*acos(0.0)
  23. #define FOR(i,n) for(int i = 0;i<n;++i)
  24. #define setbit(a,b) a|=(1<<b)
  25. #define S1(a) scanf("%d",&a)
  26. #define S2(a,b) scanf("%d %d",&a,&b)
  27. #define S3(a,b,c) scanf("%d %d %d",&a,&b,&c)
  28. #define C1(a) __builtin_popcount(a)
  29. #define gcd(a,b) __gcd(a,b)
  30. #define ALL(a) (a.begin(),a.end())
  31.  
  32. typedef long long LL;
  33. typedef vector<int> vi;
  34. const int INF = (1LL<<31)-1;
  35.  
  36. char inpt[1000005];
  37. map< string,int > mp;
  38.  
  39. int main(){
  40.  
  41.     int n;
  42.     while( S1(n)==1 )
  43.     {
  44.         mp.clear();
  45.         scanf("%s",inpt);
  46.         string subStr = "";
  47.         int mx = 0,r = 0;
  48.         //i am not using strlen because it takes time :( inpt[i] works fine.
  49.         for(int i = 0;inpt[i];++i)
  50.         {
  51.             subStr += inpt[i];
  52.             //other than making substr every time i can just erase the first character.
  53.             // say after "abc" when d comes i will make it "abcd" and then remove a, thus it will become "bcd".
  54.             if( i >= n )
  55.             {
  56.                 subStr.erase(subStr.begin(),subStr.begin()+1);
  57.             }
  58.             //accesing map consumes log(n) time. so i will store the map value in a variable and later i will only use this variable.
  59.             int cur = mp[ subStr ]++;
  60.             ++cur;
  61.             if( mx < cur )
  62.             {
  63.                 mx = cur;
  64.                 //if we copy the result string every time it takes a bit time also :P
  65.                 //i will only kow the first index from where to print the result.
  66.                 r = i-n+1;
  67.             }
  68.         }
  69.         for(int i = r;i<r+n;++i)printf("%c",inpt[i]);
  70.         puts("");
  71.     }
  72.     return 0;
  73.  
  74. }
Add Comment
Please, Sign In to add comment