Cod sursa(job #1526883)

Utilizator radoneNeacsu Radu-Stefan radone Data 17 noiembrie 2015 16:19:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb

#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int v[2000000];
int main()
{
    char subsir[2000000],text[2000000];
    f>>subsir;
    f>>text;
    int i,j,n;
    j=0;
    i=1;
    n=strlen(subsir);
    while(i<n)
    {
        if(subsir[i]==subsir[j])
        {
            v[i] = j+1;
            j++;
            i++;
        }
        else
        {
            if(j==0)
                i++;
            else
                j = v[j-1];
        }
    }
    int k,x[1001],m;
    m = strlen(text);
    i=j=k=0;
    while(i<=m)
    {
        if(j == n)
        {
            k++;
            if(k<=1000);
                x[k] = i-n;
            i=i-v[j-1];
            j=0;
        }
        else
            if(text[i]==subsir[j])
            {
                i++;
                j++;
            }
            else
                if(j == 0)
                    i++;
                else
                    j = v[j-1];
    }
    g<<k<<"\n";
    for(i=1;i<=(k<=1000?k:1000);i++)
        g<<x[i]<<" ";
    f.close();
    g.close();
    return 0;
}