Cod sursa(job #219034)

Utilizator dragosmihaiDragos Oana dragosmihai Data 4 noiembrie 2008 20:28:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <string>
#define nm 2000003
using namespace std;

char s1[nm],s2[nm];
int a[1002],n;
int pre[nm];

void prefix()
{
    int l=strlen(s1);
    int k=0;
    for(int i=2;i<l;i++)
    {
        while(k&&s1[k+1]!=s1[i])
            k=pre[k];
        if(s1[k+1]==s1[i])
            k++;
        pre[i]=k;
    }
}

void kmp()
{
    int l2=strlen(s2);
    int l1=strlen(s1)-1;
    int k=0;
    for(int i=1;i<l2;i++)
    {
        while(k&&s1[k+1]!=s2[i])
            k=pre[k];
        if(s1[k+1]==s2[i])
            k++;
        if(k==l1)
        {
            if(n<1000)
                a[n]=i-l1;
             n++;
        }
    }
}

void init()
{
    if(s1[strlen(s1)-1]=='\n')
        s1[strlen(s1)-1]=0;
    if(s2[strlen(s2)-1]=='\n')
        s2[strlen(s2)-1]=0;
    int l1=strlen(s1);
    int l2=strlen(s2);
    for(int i=l1;i>0;i--)
        s1[i]=s1[i-1];
    s1[0]=' ';
    for(int i=l2;i>0;i--)
        s2[i]=s2[i-1];
    s2[0]=' ';
}

void citire()
{
    ifstream f("strmatch.in");
    f.getline(s1,nm);
    f.getline(s2,nm);
    f.close();
    init();
    prefix();
}

void scriere()
{
    ofstream g("strmatch.out");
    int l=n<1000?n:1000;
    g<<n<<endl;
    for(int i=0;i<l;i++)
        g<<a[i]<<" ";
}

int main()
{
    citire();
    kmp();
    scriere();
    return 0;
}