Cod sursa(job #156632)

Utilizator cretuMusina Rares cretu Data 12 martie 2008 17:53:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>
#define MAX 2000001

using namespace std;

int m, n, sol[MAX], nr = 0, pi[MAX];
char a[MAX], x[MAX];

void KMP();
void Prefix();

int main()
{
    int i;
    ifstream fin("strmatch.in");
    fin >> x;
    fin >> a;
    fin.close();
    
    n = strlen(x);
    for (i = n; i; i--)
        x[i] = x[i-1];
    x[0] = ' ';
    
    m = strlen(a);
    for (i = m; i; i--)
        a[i] = a[i-1];
    a[0] = ' ';
    
    KMP();
    
    ofstream fout("strmatch.out");
    fout << nr << "\n";
    for (i = 1; i <= nr; i++)
        fout << sol[i] << " ";
    fout.close();
    
    return 0;
}

void Prefix()
{
     int i, k;
     
     k = 0;
     pi[1] = 0;
     
     for (i = 2; i <= n; i++)     
     {
         while (x[i] != x[k+1] && k) {k = pi[k];}   
         if (x[i] == x[k+1]) k++;
         pi[i] = k;
     }
}

void KMP()
{
     int i, k;
     
     Prefix(); 
     
     k = 0;
     
     for (i = 1; i <= m; i++)    
     {
         while (x[k+1] != a[i] && k) {k = pi[k];}
         if (a[i] == x[k+1]) k++;
         if (k == n)
         {
            sol[++nr] = i-k;
            k = pi[k];      
         }    
     }
}