Cod sursa(job #2168082)

Utilizator Victor24Vasiesiu Victor Victor24 Data 14 martie 2018 09:30:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int dp[2000005], rsp[2000005], cnt;

string pat, s;

void make_pat ()
{
    int i = 1, j = 0;
    int l = pat.size();

    while ( i < l )
    {
        if ( pat[i] == pat[j] )
        {
            dp[i] = j + 1;
            i++;
            j++;
        }
        else
        {
            if ( j!= 0 )
            {
                j = dp[ j-1 ];
            }
            else
            {
                i++;
            }
        }
    }

}

void kmp ()
{
    int i = 0 , j = 0;

    int ls = s.size();
    int lpat = pat.size();

    while ( i < ls )
    {
        if ( s[i] == pat[j] )
        {
            i++;
            j++;
        }
        else
        {
            if ( j!=0 )
            {
                j = dp[j-1];
            }
            else
            {
                i++;
            }
        }

        if ( j == lpat )
        {
            rsp[++cnt] = i - lpat;
        }

    }

}


int main ()
{
    f>>pat>>s;

    make_pat();
    kmp();

    g<<cnt<<'\n';
    for ( int i = 1; i <= cnt && i <= 1000 ; i++ )
    {
        g<<rsp[i]<<" ";
    }

    return 0;
}