fork download
copy 
  1. //BISMILLAHIRRAHMANIRRAHIM
  2. /*
  3.  manus tar shopner soman boro
  4.  all my suceesses are dedicated to my parents
  5.  Author :: Shakil Ahmed
  6. .............AUST_CSE27.........
  7.  prob   ::
  8.  Type   ::
  9.  verdict::
  10.  */
  11.  
  12. #include <bits/stdc++.h>
  13. #define pb push_back
  14. #define mp make_pair
  15. #define pi acos(-1.0)
  16. #define ff first
  17. #define ss second
  18. #define re return
  19. #define QI queue<int>
  20. #define SI stack<int>
  21. #define SZ(x) ((int) (x).size())
  22. #define all(x) (x).begin(), (x).end()
  23. #define sqr(x) ((x) * (x))
  24. #define ms(a,b) memset((a),(b),sizeof(a))
  25. #define G() getchar()
  26. #define MAX3(a,b,c) max(a,max(b,c))
  27. #define II ( { int a ; read(a) ; a; } )
  28. #define LL ( { Long a ; read(a) ; a; } )
  29. #define DD ({double a; scanf("%lf", &a); a;})
  30.  
  31. double const EPS=3e-8;
  32. using namespace std;
  33.  
  34. #define FI freopen ("input.txt", "r", stdin)
  35. #define FO freopen ("output.txt", "w", stdout)
  36.  
  37. typedef long long Long;
  38. typedef long long int64;
  39. typedef unsigned long long ull;
  40. typedef vector<int> vi ;
  41. typedef set<int> si;
  42. typedef vector<Long>vl;
  43. typedef pair<int,int>pii;
  44. typedef pair<string,int>psi;
  45. typedef pair<Long,Long>pll;
  46. typedef pair<double,double>pdd;
  47. typedef vector<pii> vpii;
  48.  
  49. // For loop
  50.  
  51. #define forab(i, a, b)	for (__typeof (b) i = (a) ; i <= b ; ++i)
  52. #define rep(i, n)		forab (i, 0, (n) - 1)
  53. #define For(i, n)		forab (i, 1, n)
  54. #define rofba(i, a, b)	for (__typeof (b)i = (b) ; i >= a ; --i)
  55. #define per(i, n)		rofba (i, 0, (n) - 1)
  56. #define rof(i, n)		rofba (i, 1, n)
  57. #define forstl(i, s)	for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
  58.  
  59. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
  60. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  61.  
  62. //Fast Reader
  63. template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
  64.  
  65. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  66. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  67. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  68. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  69.  
  70. /* **************************************  My code start here ****************************************** */
  71.  
  72. const int NX = 1e5 + 10 ;
  73. int Z[NX] , sz , CumSum[NX] ;
  74. char inp[NX];
  75. void Z_algorithm()
  76. {
  77.     sz = strlen( inp );
  78.     Z[0] = sz ; // always ;
  79.     int i , l , r ;
  80.     for ( i = 1 , l = 0 , r = 0 ; i < sz ; i++ )
  81.     {
  82.         if( i <= r ) Z[i] = min( r - i + 1 , Z[i-l] );
  83.         while( i + Z[i] < sz && inp[Z[i]] == inp[ i + Z[i]] ) ++Z[i];
  84.         if( i + Z[i] - 1 > r ) // need to update r
  85.         {
  86.             l = i ;
  87.             r = i + Z[i] - 1 ;
  88.         }
  89.     }
  90. }
  91.  
  92. int main()
  93. {
  94.    // I will always use scanf and printf
  95.    // May be i won't be a good programmer but i will be a good human being
  96.   //cout << Num( 72 ) << endl ;
  97.  
  98.     scanf("%s",inp);
  99.     Z_algorithm();
  100.     vector < pii > ans ;
  101.     int i ;
  102.    // CumSum[sz]++;
  103.     for ( i = 0 ; i < sz ; i++ )
  104.     {
  105.         if( Z[i] ) {
  106.         CumSum[1]++;
  107.         CumSum[Z[i] + 1]--;
  108.         }
  109.     }
  110.     for ( i = 1 ; i <= sz ; i++ ) CumSum[i] += CumSum[i-1];
  111.     for ( i = sz - 1 ; i >= 0 ; i-- )
  112.     {
  113.         if( Z[i] == sz - i ) // suffix matches
  114.         {
  115.             ans.pb( mp( sz - i , CumSum[Z[i]] )  );
  116.         }
  117.     }
  118.     sz = ans.size();
  119.     cout << sz << endl ;
  120.     rep( i , sz ) cout << ans[i].ff << " " << ans[i].ss << endl ;
  121.  
  122.     return 0;
  123. }
Success #stdin #stdout 0s 3980KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/aMKVj9
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!