Cod sursa(job #2130972)

Utilizator mateiuMateiu Ioan mateiu Data 14 februarie 2018 09:49:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <cstring>
using namespace std;
char v[2000002],w[2000002];
int pref[2000002],poz[1002],n,m,c=0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void cstr()
{
    int j=0;
    for(int i=2;i<=n;i++)
    {
        while(v[j+1]!=v[i]&&j>0)
        {
            j=pref[j];
        }
        if(v[j+1]==v[i])
        {
            j++;
        }
        pref[i]=j;
    }
}
void cauta()
{
    int j=0;
    for(int i=1;i<=m;i++)
    {
        while(v[j+1]!=w[i]&&j>0)
        {
            j=pref[j];
        }
        if(v[j+1]==w[i])
            j++;
        if(j==n)
        {
            c++;
            if(c<=1000)
            poz[c]=i-n;
            j=pref[j];
        }
    }
}
int main()
{
    f>>v+1;
    f>>w+1;
    n=strlen(v+1);
    m=strlen(w+1);
    cstr();
    cauta();
    g<<c<<"\n";
    if(c<=1000)
    {
        for(int i=1;i<=c;i++)
        {
            g<<poz[i]<<" ";
        }
    }
    else
    {
        for(int i=1;i<=1000;i++)
        {
            g<<poz[i]<<" ";
        }
    }
    return 0;
}