Submission #856724

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair

char incaa[505000];

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

int main()
{

//    gets(incaa);
//    string s(incaa);
    string s;
    getline(cin, s);
    int n = s.size();
    bool f1=true;
    forn(i,0,n) {
        if(s[i]!=s[0]) f1=false;
    }
    if(f1) {
        cout<<n<<endl;
        cout<<1<<endl;
        return 0;
    }
    vi pf1 = prefix_function(s);
    reverse(all(s));
    vi pf2 = prefix_function(s);
    
    int l1 = n;
    int sl1 = pf1[n-1];
    int dl1 = n-sl1;
    if(sl1 == 0 || l1%dl1 !=0) {
        cout<<1<<endl<<1<<endl;
        return 0;
    }
    
    cout<<2<<endl;
    
    
    
    int cnt =0 ;
    forn(i,1,n) {
        int l = i;
        int r = n-i;
        int sl = pf1[l-1];
        int sr = pf2[r-1];
        int dl = l - sl;
        int dr = r - sr;
        if((l%dl == 0 && sl>0)|| (r%dr ==0 &&sr>0)) continue;
        cnt++;
    }
    cout<<cnt<<endl;
    
    
    
    
    
}

Submission Info

Judge Result