Advertisement
Guest User

Untitled

a guest
Jul 4th, 2015
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fr(a,b,c) for(int (a) = (b); (a) < (c); ++(a))
  6. #define rp(a,b) fr(a,0,b)
  7. #define fre(a,b) for(int a = adj[b]; ~a; a = ant[a])
  8. #define cl(a,b) memset((a), (b), sizeof(a))
  9. #define sc(a) scanf("%d", &a)
  10. #define sc2(a,b) scanf("%d%d", &a, &b)
  11. #define sc3(a,b,c) scanf("%d%d%d", &a, &b, &c)
  12. #define scs(s) scanf("%s", s)
  13. #define pri(x) printf("%d\n", x)
  14.  
  15. #define iter(a) __typeof((a).begin())
  16. #define fore(a,b) for(iter(b) a = (b).begin(); a != (b).end(); ++a)
  17.  
  18. #define st first
  19. #define nd second
  20. #define mp make_pair
  21. #define pb push_back
  22.  
  23. #define db(x) cerr << #x << " == " << x << endl
  24. #define dbs(x) cerr << x << endl
  25. #define _ << ", " <<
  26.  
  27. const int oo = 0x3f3f3f3f;
  28.  
  29. typedef long long ll;
  30. typedef pair<int,int> pii;
  31. typedef vector<int> vi;
  32. typedef vector< vi > vii;
  33. typedef unsigned long long ull;
  34.  
  35. #define MOD 1000000007
  36.  
  37. char str[100010];
  38. int n;
  39. unordered_set<int> s;
  40.  
  41. bool test(int x) {
  42.     s.clear();
  43.     rp(i,n-x+1) {
  44.         int h = 0;
  45.         fr(j,i,i+x) {
  46.             h = ((h<<1) + (str[j] == '-'))%MOD;
  47.         }
  48.         if (s.count(h)) return true;
  49.         s.insert(h);
  50.     }
  51.     return false;
  52. }
  53.  
  54. void proc(int x) {
  55.     s.clear();
  56.     rp(i,n-x+1) {
  57.         int h = 0;
  58.         fr(j,i,i+x) {
  59.             h = ((h<<1) + (str[j] == '-'))%MOD;
  60.         }
  61.         if (s.count(h)) {
  62.             fr(j,i,i+x) {
  63.                 printf("%c", str[j]);
  64.             }
  65.             puts("");
  66.             return;
  67.         }
  68.         s.insert(h);
  69.     }
  70. }
  71.  
  72. int main() {
  73.     scs(str);
  74.     n = strlen(str);
  75.     int ini = 0, fim = n;
  76.     while (ini < fim) {
  77.         int m = (ini+fim+1)>>1;
  78.         if (test(m)) ini = m;
  79.         else fim = m-1;
  80.     }
  81.     if (ini < 3) puts("*");
  82.     else proc(ini);
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement