Cod sursa(job #2401673)

Utilizator victoreVictor Popa victore Data 9 aprilie 2019 21:55:49
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>

using namespace std;

const int NMAX = 2e6+5;

string s[2];
int pref[NMAX];
stack<int> st,st2;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int M,N,i,j;
    cin>>s[0]>>s[1];
    //match 0 in 1

    N = s[0].size();
    M = s[1].size();

    for(i = 1 , j = 0 ; i < N ; ++i)
    {
        if(s[0][i] == s[0][j])
            pref[i] = ++j;
        else
        {
            pref[i] = 0;
            j = 0;
        }
    }
    for(i = j = 0 ; i < M ; ++i)
    {
        if(s[1][i] == s[0][j])
        {
            if(j == N - 1)
            {
                st.push(i - j);
                j = pref[j];
            }
            else
                j++;
        }
        else
        {
            if(j != 0)
                j = pref[j-1];
        }
    }
    int sz = st.size();
    printf("%d\n",sz);
    while(!st.empty())
    {
        st2.push(st.top());
        st.pop();
    }

    while(!st2.empty())
    {
        printf("%d ",(st2.top()));
        st2.pop();
    }
}