Cod sursa(job #2174523)

Utilizator Victor24Vasiesiu Victor Victor24 Data 16 martie 2018 12:25:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

string pat, s;

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


void make_pat()
{
     int l = pat.size();

     int i = 1 , j = 0;

     while ( i < l )
     {
         if ( pat[j] == pat[i] )
         {
             supre[i] = j+1;

             i++;
             j++;

         }
         else
         {
             if ( j!=0 )
             {
                 j = supre[ j-1 ];
             }
             else
             {
                 i++;
             }
         }
     }
}

void kmp()
{
    int lpat = pat.size();
    int ls = s.size();
    int i = 0 , j = 0;

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

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

    }

}

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;
}