Cod sursa(job #2401746)

Utilizator victoreVictor Popa victore Data 9 aprilie 2019 23:34:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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
        {
            if(j > 0)
            {
                j = pref[j-1];
                i--;
            }
        }
    }
    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];
                i--;
            }
        }
    }
    int sz = st.size();
    printf("%d\n",sz);
    while(!st.empty())
    {
        st2.push(st.top());
        st.pop();
    }

    i = 1;
    while(!st2.empty() && i <= 1000)
    {
        printf("%d ",(st2.top()));
        st2.pop();
        i++;
    }
    return 0;
}