Cod sursa(job #2164627)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 13 martie 2018 08:51:33
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );

char T[N], P[N];
int L[N], d[N];
int n, m;

void precalculare()
{
    int i, k = 0;
    L[0] = 0;
    for ( i = 1; i < m; ++i )
         { if ( P[i] == P[k] ) k++;
           else
               { while ( P[i] != P[k] && k > 0 )
                        k = L[k-1];
                 if ( P[i] == P[k] ) k++;
               }
           L[i] = k;
         }
}

void KMP()
{
    int i, k;
    for ( i = 0; i < n; ++i )
         { if ( T[i] == P[k] ) k++;
           else
               { while ( k > 0 && T[i] != P[k] )
                        k = L[k-1];
                 if ( T[i] == P[k] ) k++;
               }
           d[i] = k;
         }
}

int main()
{   int i, ct = 0;
    fin >> P >> T;
    fin.close();
    n = strlen(T);
    m = strlen(P);
    precalculare();
    KMP();
    for ( i = 0; i < n; ++i )
         if ( d[i] == m )
             ct++;
    fout << ct << '\n';
    for ( i = 0; i < n; ++i )
         if ( d[i] == m )
             fout << i - m + 1 << ' ';
    fout.close();
    return 0;
}