//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 250000+10

int N;
char str1[MAXN], str2[MAXN];
char temp[MAXN*2];

int kmp(char* s, char* t, int pos);
void get_next(char* t, int* next, int t_len);
int main()
{
#ifdef LOCAL
    freopen("1423_String_Tale_2.in", "r", stdin);
    freopen("1423_String_Tale_2.out", "w", stdout);
#endif

    scanf("%d", &N);
    scanf("%s%s", str1, str2);

    int s1_len = strlen(str1);
    int s2_len = strlen(str2);

    if(s1_len != s2_len){
        printf("%d\n", -1);
        return 0;
    }

    strcpy(temp, str1);
    strcat(temp, str1);
    int ans;
    ans = kmp(temp, str2, 0);
    if(ans != 0 && ans != -1)
        printf("%d\n", s1_len-ans);
    else
        printf("%d\n", ans);

    return 0;
}

int kmp(char* s, char* t, int pos)
{
    int s_len = strlen(s);
    if(pos<0 || pos>s_len-1){
        fprintf(stderr, "%s", "Error: invalid pos.");
        system("pause");
    }

    int t_len = strlen(t);
    int *next = (int*)malloc(sizeof(int) * t_len);
    get_next(t, next, t_len);

    int i = pos;
    int j = 0;

    while(i<s_len && j<t_len){
        if(j<0 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }

//    free(next);
    if(j >= t_len)
        return i-t_len;
    else
        return -1;
}

void get_next(char* t, int* next, int t_len)
{
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < t_len){
        if(k==-1 || t[j]==t[k]){
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

###############################################
Can anyone tell me WHY???

Edited by author 11.07.2017 19:31

Please, give me some hints on how to solve it. Thanks in advance.

I have got a verdict Compiler Failed on Clang compiler.  Never have got such a verdict.  Every other compiler submit gets AC. Can't post code here because it is a working solution.

I was trying to do the following.
Construct suffix automation for each command.
Binary search for length of each key substring.
Binary search works as follows.
For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command.

Check my submissions and learn how evil the problem is!

Use unordered map and unordered set.
max_load_factor(0.25)
reserve (1<<x)

Could someone explain this idea?
tbl[0] = 1;
for (int i = 1; i <= N; i++)
{
    for (int j = N; j >= i ; j--)
    {
            tbl[j] += tbl[j-i];
    }
}
cout<<tbl[N]-1<<endl;

I had a MLE 7 test - I split the tree into 3 parts
And choose the best 3 answers
Accepted 0.593 !!!!

-------------------------
Enough for the division into 2 parts

Edited by author 30.07.2011 10:18

#include <iostream>
#include <vector>
#include <queue>
#define INF (1<<29)
using namespace std;

struct Arista
{
    int hasta,costo;
};

Arista armar(int h,int c)
{
    Arista ar;
    ar.hasta=h;
    ar.costo=c;
    return ar;
}

struct Grafo
{
    int suma=0;

    vector <vector <Arista>> adj;
    vector <int> dist;
    vector <bool> visitado;
    bool encontro=false;

    int nodos,aristas;
    int S,F;

    void leer()
    {
        cin >> nodos >> aristas;
        adj.resize(nodos+1);
        dist.resize(nodos+1,INF);
        visitado.resize(nodos+1,false);

        int desde,hasta,costo;
        for(int c=0; c<aristas; c++)
        {
            cin >> desde >> hasta >> costo;
            adj[desde].push_back(armar(hasta,costo));
        }

        cin >> S >> F;
        dist[S]=0;
    }

    void bdfs(int nodo, int padre)
    {

        visitado[nodo]=true;

        for(int c=0; c<adj[nodo].size(); c++)
        {
            int vecino=adj[nodo][c].hasta;
            int costo=adj[nodo][c].costo;
            if(dist[vecino]>dist[nodo]+costo&&visitado[vecino]==false)
            {
                dist[vecino]=dist[nodo]+costo;
                bdfs(vecino,nodo);
            }
        }
    }


    void start()
    {
        if(dist[F]<INF) cout << dist[F];
        else cout << "No solution";
    }

};

int main()
{
    Grafo g;
    g.leer();
    g.bdfs(g.S,-1);
    g.start();
    cout << endl;
    return 0;
}


BFS+DFS
Some test, guys?

j-1 bit must be 1 if prefix of the string could be cut by j palindroms. in notation 9-->1110 , but 9 must be 10000000, isn`t it???

I was using QUEUE.
It was Memory limit exceed #8 or something similar.
Replaced queue by simple an static array of one million elements.
I was using state struct.
There are three members of unsigned char type.
So,  with C limitations, I got AC with 16 MB.

На руби вообще не имеет смысла что-то решать?

add test x = y; x + y < c; x, y < c
example input: 900000000 900000000 1000000000, i had AC with output 900000000 900000000

When I was using STD::SET and STD::MAP,  it was TLE #18.
When I switched to STD::UNORDERED_SET and STD::UNORDERED_MAP,  it was ACCEPTED 0.6 sec 38 MB.
I was using reserve (1<<16) and max load factor of 0.25.

Hello,
Does anybody know what is the 2nd test? I can't get my head round this issue.

If you want to run your own contest system, you can try my open-source server: http://codejudge.azurewebsites.net
Source code: https://github.com/Backs/judge.net
Work in progress, I'll add new features.
If you want to try it, you can write me, I'll help to install and configure it.

Братаны-кодеры в этой задаче нужен особый подход к считыванию
Из условия неясно,какой формат,но пока что он следущий(.=пробел):
ххх.ххх.ххх и т.д.
ууу.ууу.ууу.ууу и т.д.
Не используйте на Паскале eof,eoln.
Часть моего говнокода:
 ...
 s:string[4];
 ...
 len:=1;
 read(s);
 inc(c[90*90*(ord(s[1])-33)+90*(ord(s[2])-33)+(ord(s[3])-33)]);
 f:=length(s)=4;
 while f do begin
  inc(len);
  read(s);
  inc(c[90*90*(ord(s[1])-33)+90*(ord(s[2])-33)+(ord(s[3])-33)]);
  f:=length(s)=4;
 end;
 ...

C++.  I was using recursive DFS. vector <vector<int> >.   I forgot to pass graph vector by reference and got MLE#8. After noticing that I am passing graph vector by value and simply adding an ampersand before vector name AC 1MB memory used.

Edited by author 03.07.2017 15:43

98000 3334 3334
1
25000 3333
3
1 97999 1
2 30000 1
2 25000 1

Answer - You should rent the apartment #1 alone. or You should rent the apartment #2 alone. or You should rent the apartment #3 alone.

21111 1111 7777
5
1111 7777
10000 6556
20000 3131
80000 2
76400 1
4
1 21110 6000
1 21111 6665
2 21111 1220
2 1110 0

Answer - You should rent the apartment #3 alone.

1001 1001 1001
1
1001 1
1
2 1001 1

Answer - You should rent the apartment #1 alone.

I hope it can help. My program, which got WA 6, failed on this tests.