Cod sursa(job #219031)

Utilizator dragosmihaiDragos Oana dragosmihai Data 4 noiembrie 2008 20:15:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 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&&n<1000)
            a[n++]=i-l1;
    }
}

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");
    g<<n<<endl;
    for(int i=0;i<n;i++)
        g<<a[i]<<" ";
}

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