Solved with Z-function in 17 rows of code (if don't count 10 rows for Z-function)

I am using hash...help

For TC:
abracadabra
abrabracada

why don't the prefixes are:
abra abracada a?

and also

why for TC:
abracadabra
arbadacarba

the prefix is not:
a?

https://e-maxx-eng.appspot.com/string/prefix-function.html
https://ru.coursera.org/learn/algorithms-on-strings/lecture/exytr/prefix-function
https://brilliant.org/wiki/knuth-morris-pratt-algorithm/
https://stackoverflow.com/questions/13792118/kmp-prefix-table

GooD LucK!!!

aaaaa
aaa

No
aaa

aaaaa
aaaaaaaaa

No
aaaa aaaaa

aabaa
aabaabaabaaaaabaa

No
aab aab aaba aa aabaa

aabaa
aabaabaab

No
aab aab aab

abcabcabccs
abcaabcaabcaa

No
abca abca abca a

aabaa
aabaabaaaa

No
aab aabaa aa

WA 10
WA 14

don't use hashes with modulo = 2^32, change it to 10^9 + 7

const Nmax=1000000;
var
 s:array[0..Nmax-1] of char;
 z,ans,rans:array[0..Nmax-1] of longint;
 N,M,i,L,R,last,len:longint;
 ch:char;

function min(x,y:longint):longint;
begin
 if(x>y) then x:=y;
 min:=x;
end;

procedure Init;
begin
 N:=-1;
 read(ch);
 while(ord(ch)>=ord('a'))and(ord(ch)<=ord('z')) do begin
  inc(N);
  s[N]:=ch;
  read(ch);
 end;
 readln;

 inc(N);
 M:=0;
 s[N]:='#';
 read(ch);
 while(ord(ch)>=ord('a'))and(ord(ch)<=ord('z')) do begin
  inc(N);
  inc(M);
  s[N]:=ch;
  read(ch);
 end;
end;

BEGIN
 Init;

 z[0]:=N;
 L:=0;
 R:=0;

 for i:=1 to N do
 begin
  if(i<=R) then z[i]:=min(z[i-l],R-i+1)
  else z[i]:=0;
   while(i+z[i]<=N)and(s[i+z[i]]=s[z[i]]) do inc(z[i]);
   if(i+z[i]-1>R)and(z[i]>0) then begin
    R:=i+z[i]-1;
    L:=i;
   end;
 end;

 len:=0;
 last:=N;
 R:=0;
 i:=N;
 while(i>=N-M) do begin
  if(z[i]>=last-i+1) then begin
   inc(r);
   ans[r]:=i;
   rans[r]:=last;
   inc(len,last-i+1);
   last:=i-1;
  end;
  dec(i);
 end;

 if(len<M) then writeln('Yes')
 else begin
  writeln('No');
  for i:=r downto 1 do begin
   for l:=ans[i] to rans[i] do write(s[l]);
   write(' ');
  end;
 end;
END.

В чём баг хз.Уже сколько пытаюсь сдать-всегда WA3!
Решал так:s1 и s2-входные строки,создаю строку s1#s2,вычисляю z-функцию для s=s1#s2,иду с конца строки до символа # и пытаюсь "покрыть" "не покрытые" символы. Если всю строку покрыл,то ответ No,иначе Yes

Code:
 const Nmax=155000;
var
 Z,L1,R1:array[1..Nmax] of longint;
 A:array[1..Nmax] of char;
 N,M,Middle,L,R,i,j,k:longint;
 ch:char;

function Min(x,y:longint):longint;
begin
 if(x>y) then x:=y;
 Min:=x;
end;

BEGIN
 N:=0;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;
 readln;

 inc(N);
 A[N]:='#';
 M:=N;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;

 Z[1]:=N;
 R:=0;
 L:=0;

 for i:=2 to N do begin
  if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1])
  else Z[i]:=0;
  while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]);
  if(i+z[i]-1>r) then begin
   L:=i;
   R:=i+z[i]-1;
  end;
 end;

 k:=0;
 L1[k]:=N+1;
 R1[k]:=N+1;

 i:=N;
 while(i>=M+1) do begin
  if(i+z[i]-1>=L1[k]-1) then begin
   inc(k);
   L1[k]:=i;
   R1[k]:=L1[k-1]-1;
  end;
  dec(i);
 end;

 if(L1[k]=M+1) then begin
  writeln('No');
  while(k>0) do begin
   for i:=L1[k] to R1[k] do write(A[i]);write(' ');
   dec(k);
  end;
 end
 else begin
  writeln('Yes');
 end;
END.

I can't find any error. My program solve all tests,my I got WA1!!!
My code:
 var
 Z:array[1..151000] of longint;
 A,C:array[1..151000] of char;
 N,L,R,i,j,k,ind,M,t:longint;
 ch:char;
 find:boolean;


function Min(x,y:longint):longint;
begin
 if(x>y) then x:=y;
 Min:=x;
end;

BEGIN
 N:=0;

 ch:='a';
 while(ord(ch)>50) do begin
  read(ch);
  if(ord(ch)>50) then begin
   inc(N);
   A[N]:=ch;
  end;
 end;

 A[N+1]:='+';
 ind:=N+1;
 inc(N);
 readln;

 ch:='a';
 while(ord(ch)>50) do begin
  read(ch);
  if(ord(ch)>50) then begin
   inc(N);
   A[N]:=ch;
  end;
 end;


 Z[1]:=N;
 R:=0;
 L:=0;

 for i:=2 to N do begin
  if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1])
  else Z[i]:=0;
  while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]);
  if(i+z[i]-1>r) then begin
   L:=i;
   R:=i+z[i]-1;
  end;
 end;


 find:=true;
 i:=N;
 while(i>=ind+1) do begin
  k:=i;
  while(i>=ind+1)and(Z[i]<k-i+1) do dec(i);
  if(i<ind+1) then find:=false;
  dec(i);
 end;

 if(find) then begin
   writeln('No ');
   i:=N;
   M:=1;
   while(i>=ind+1) do begin
    k:=i;
    while(i>=ind+1)and(Z[i]<k-i+1) do dec(i);
    t:=M;
    for j:=k downto i do begin
     C[t]:=A[j];
     inc(t);
    end;
    C[t+1]:=' ';
    M:=t+2;
    dec(i);
   end;

   for i:=M-2 downto 1 do begin
    write(C[i]);
   end;
 end
 else begin
  write('Yes');
 end;
END.

ababa
ababab

if you use kmp, you should pay attention when your index for the first word round up. It takes hours to find the problem.

Why OLE 24?

#pragma comment(linker, "/STACK:64777216")
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string>
#include<sstream>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<memory.h>
#include<ctime>
#include<cassert>

#define pb push_back
#define sz(a) (int)a.size()
#define bs binary_search
#define np next_permutation
#define mp make_pair
#define all(a) a.begin(),a.end()
#define read(a) scanf("%d", &a)
#define writeln(a) printf("%d\n", a);
#define forn(i, n) for (int i = 0; i < n; ++i)
#define forv(i, v) for (int i = 0; i < sz(v); ++i)
#define _(a, b) memset(a, b, sizeof a)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

template<class T> inline T sqr(T x) { return x * x; }

const double pi = acos(-1.0), eps = 1e-18;
const int INF = 1000 * 1000 * 1000, MAXN = 100005, MOD = INF + 7;

string s, t, ls, ans = "";
int kmp[75000 * 2 + 5];
vector<int> pos;

char al[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};

void prepare(string s) {
#ifdef _DEBUG
   freopen("input.txt", "r", stdin);
   freopen("output.txt","w",stdout);
#else
   if (sz(s) != 0) {
       freopen((s + ".in").c_str(), "r", stdin);
       freopen((s + ".out").c_str(), "w", stdout);
   }
#endif
}

void gen () {
    srand(time(NULL));
    string TMP = "";
    forn (i, 70000) {
        int k = rand() % 8;
        cout << al[k];
        TMP += al[k];
    }
    cout << '\n';
    cout << TMP;
}

void solve()
{
    cin >> s >> t;
    ls = s + "*" + t;
    kmp[0] = 0;
    for (int i = 1; i < sz(ls); i++) {
        int k = kmp[i-1];
        while (k > 0 &&  ls[i] != ls[k]) {
            k = kmp[k-1];
        }
        if (ls[i] == ls[k])
            ++k;
        kmp[i] = k;
    }
    for (int i = sz(s) + 1; i < sz(ls); i++) {
        if (kmp[i] == 0) {
            cout << "Yes";
            return;
        }
        if (i != sz(s) + 1 && kmp[i] <= kmp[i-1])
            pos.pb(kmp[i - kmp[i]]);
    }
    pos.pb(kmp[sz(ls)-1]);
    cout << "No\n";
    string tmp = "";
    int cnt = 0;
    forn (i, sz(pos)) {
        bool f = false;
        cnt += pos[i];
        forn (j, pos[i]) {
            cout << s[j];
            f = true;
        }
        if (i != sz(pos) - 1 && pos[i])
            cout << " ";
    }
}

int main()
{
   prepare("");

   //gen();
   solve();

   return 0;
}

Edited by author 09.07.2014 23:18

Do NOT use STL's strings, use standart C char arrays instead. That makes a HUGE difference in the time and memory complexity. I hope that this will be helpful to somebody:)

    abcd
    aaaa

  The answer is obvious.
  Good luck!

[code delete]

Edited by author 09.05.2013 15:31

What the hell is test 9?
In my computer I got 0.06s in worst case but still TLE 9!

abracadabra
arbadacarba

In example 2 , why is this answer wrong :
NO
a r b a d a c a r b a

All of them are "its nonempty prefix" ?

Even this answer is ok right?

Pay attention to the fact that sizes of strings may distinguish.

abcd
aaaaabcdaaaa
ans : a a a a abcd a a a a
When I print answers,I print them from the end)))
Sorry for my poor English))))

Edited by author 22.06.2012 15:47