Unexpected result: the solution using z-function is O(n) but gives TLA on the 8th test. The solution doesn't pass so I will leave the code with it here. I'm wondering if it really doesn't pass the 8th test because it is too slow though is O(n), or if there's just some kind of error in my algorithm.

vi ZFunction(string &p, string &s) {
  int n = (int) p.size();
  vector<int> z(n + 1);
  for (int i = 0, l = 0, r = 0; i < n; ++i) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && p[z[i]] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return z;
}

  ....
  vector<int> z_func = ZFunction(s1, s2);
  vector<int> z_func2 = ZFunction(s2, s1);
  for (int i = 0; i < n; ++i) {
    if (z_func[i] == n - i && z_func2[n - i] == i) {
      cout << i;
      return;
    }
  }
  cout << "-1";

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:27

such data:
3
aaa
aaa

the answer is 0 rather than 3

For those who use KMP, and get a WA -

I can confirm that this is a good implementation of KMP -
https://www.tutorialspoint.com/c-program-for-kmp-algorithm-for-pattern-searching
(I use Plain C)

Edited by author 29.11.2022 21:40

use hash :)

Cannot break this case. Any hint?

Please give me test 8!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

void Z_function (string &str, vi &z) {
    int n = str.size();
    z.resize(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && str[z[i]] == str[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = z[i] + i - 1;
    }
}

string str, s;
vi z;

int main() {
    int n;
    cin >> n >> str >> s;
    str += '$'; str += s; str += s;
    Z_function(str, z);
    fo(i, (int)z.size()) {
        if (z[i] == n) {
            cout << i - n - 1 << endl;
            re 0;
        }
    }
    cout << -1 << endl;
    re 0;
}

Get me test, please! I use kmp.

int main()
{
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    s1 += s1;
    int pos = (int) s1.find(s2);
    switch ( pos )
    {
    case -1:
        cout << -1;
        break;
    case 0:
        cout << 0;
        break;
    default:
        cout << n-pos;
    }
    return 0;
}

//#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

any idea what could be my mistake? i'm using
i=n; i< 2n; i++
h2=((mod + h2 - dn * a[i-n] % mod) * d % mod + a[i]) % mod;

where d=256, dn=d^(n-1) mod=10^9+9

A can't understand what's the problem and why I don't pass it. Help me, please.

4
aaba
abaa

answer
3

//package timus;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.StringTokenizer;

public class p1423 {
    static char[] t;
    static char[] p;
    static int[] pi;
    static int N;

    public static void main(String[] args) throws FileNotFoundException {
        InputStream is = System.in;
        FastScanner sc = new FastScanner(new InputStreamReader(is));
        N = sc.nextInt();
        String tt = sc.next();
        tt += tt;
        t = tt.toCharArray();
        p = sc.next().toCharArray();
        pi = new int[N];
        System.out.println(KMPMatcher());
    }

    static int KMPMatcher() {
        computePrefixFunction();
        int equals = 0;
        for (int i = 0; i < N + N; i++) {
            while (equals > 0 && p[equals] != t[i])
                equals = pi[equals - 1];
            if (p[equals] == t[i])
                equals++;
            if (equals == N) {
                if (i == N - 1) {
                    return 0;
                } else {
                    return N + N - (i + 1);
                }
            }
        }
        return -1;
    }

    static void computePrefixFunction() {
        int k = 0;
        for (int q = 1; q < N; q++) {
            while (k > 0 && p[k] != p[q])
                k = pi[k - 1];
            if (p[k] == p[q])
                k++;
            pi[q] = k;
        }
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(Reader in) {
            br = new BufferedReader(in);
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

# include <iostream>
# include <fstream>
# include <cmath>
# include <vector>
# include <algorithm>
# include <math.h>
# include <time.h>
# include <string>
# include <string.h>
# include <map>
# include <queue>
# include <stack>

using namespace std;
const int MAXN = 1000000007;//, Maxn = 1000000009;

long long n, a, san, num, dereje = 1, x;

bool zero, one;

string s, h;

int main()
{
    cin >> n >> s >> h;

    a = n-1;

    for (int i=0; i<n; i++) {
        san = (san + (dereje * (s[i]-'a'+1))) % MAXN;
        num = (num + (dereje * (h[i]-'a'+1))) % MAXN;
        dereje = (dereje * 27) % MAXN;
    }

    if (san == num)    {cout << 0 << '\n'; return 0;}

    for (int i=0; i<n; i++) {
        san = (san * 27) % MAXN,
        san = (san - (((s[a]-'a'+1) * dereje) % MAXN)),
        san = (san + MAXN) % MAXN,
        san = (san + (s[a]-'a'+1)) % MAXN;

        if (san == num)    {cout << i+1 << '\n'; return 0;}
        a--;
    }

    cout << -1 << '\n';

    return 0;
}


WA 8.why?
i used HASH!


plz help me!

I'm using KMP I don't know why I get TLE?



#include <iostream>



int main(int argc, const char * argv[]) {

    long long int NumofChars;
    long long int finAns=-1;

    scanf("%lld",&NumofChars);

    char lettersS[2*NumofChars];
    char lettersT[NumofChars];
    char letter_tmp;





    for (long long int i=0;i<NumofChars;i++)
    {
        scanf(" %c",&letter_tmp);
        lettersT[i]=letter_tmp;
    }

    for (long long int i=0;i<NumofChars;i++)
    {
        scanf(" %c",&letter_tmp);
        lettersS[i]=letter_tmp;
        lettersS[i+NumofChars]=letter_tmp;
    }




    long long int prefix[NumofChars];
    prefix[0]=0;
    prefix[1]=0;

    long long int pi=0;
    long long int pj=1;

    while(pj<NumofChars-1)
    {
        if(lettersT[pi]==lettersT[pj])
        {
            prefix[pj+1]=prefix[pj]+1;

            pi++;
            pj++;

        }
        else
        {

            pi=0;
            if(lettersT[pi]==lettersT[pj])
            {
                prefix[pj+1]=1;

                pi++;
                pj++;


            }
            else
            {
                prefix[pj+1]=0;

                pj++;

            }

        }
    }







    finAns=-1;

    long long int i=0;
    while(i<NumofChars)
    {


        long long int Matchcount=0;
        long long int j_init=0;
        for (long long int j=j_init;j<NumofChars;j++)
        {
            if(lettersS[i+j]==lettersT[j])
            {
                Matchcount++;
            }
            else
            {
                if(j-prefix[j]>0)
                {
                    i=i+j-prefix[j];
                    j_init=prefix[j];

                }
                else
                {
                    i++;
                }

                break;
            }
        }


        if(Matchcount==NumofChars)
        {
            finAns=i;

            break;
        }
    }
    std::cout<<finAns;
    return 0;
}

If you get WA 8 you might not be checking correctly for string equality once the hash goes through (false positive).

Можете отправить работающую программу,если не сложно.Долго уже пытаюсь,не получается:(

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_READ 250000
#define MASIVE(a, b) (b *) malloc(sizeof(b *)*(a))
#define STRING(a) MASIVE((a), char);

#define R_CONCAT(T,S,A) strcat(A, T); \
                        strcat(A, " "); \
                        strcat(A, S); \

int * Z_simple(char * str, int len) {
  int * z = MASIVE(len, int);

  for (int i = 1;  i < len; i++) {
    int * val = z + i;
    *val = 0;
    for (int j = 0; i + j < len; j++) {
      if (str[i + j] != str[j]) {
        break;
      }
      (*val)++;
    }
  }
  return z;
}

int * Z(char * str, int len) {
  int * z = MASIVE(len, int);
  int l = 0, r = 0;

  for (int k = 1; k < len; k++) {
    if (k > r) {
      l = k;
      int pos = 0;

      while (k + pos < len && str[pos] == str[k + pos]) {
        pos++;
      }

      if (pos == 0) {
        r = l;
        z[k] = 0;
      } else {
        r = k + pos - 1;
        z[k] = pos;
      }

    } else {
      int m = k - l;
      int b = z[l] - m;
      if (z[m] < b) {
        z[k] = z[m];
      } else {

        int pos1 = b;
        int pos2 = k + b;
        int pos = 0;

        while(pos2 + pos < len && str[pos1 + pos] == str[pos2+pos]) {
          pos ++;
        }

        if (pos != 0) {
          l = k;
          r = pos2 + pos - 1;
          z[k] = b + pos;
        } else {
          z[k] = b;
        }

      }
    }

  }

  return z;
}



int main() {

    int n;
    int result = -1;
    scanf("%d", &n);

    char * T = STRING(n);
    char * S = STRING(n);

    scanf("%s%s", T, S);

    int len_N = 2*n + 1;

    char * N = STRING(len_N);

    R_CONCAT(T,S,N);

    int * z = Z(N, len_N);
    z = z + (n + 1);

    for (int i = 0; i < n; i++) {
        if (z[i] == n - i) {
            int k = z[i];
            int b = 0;
            for (int j = 0; j < i; j++) {
                if (T[k + j] != S[j]) {
                     b = 1;
                     break;
                }
            }
            if (b == 0)
                result = i;
            break;
        }
    }

    printf("%d", result);
}