Cod sursa(job #1463886)

Utilizator doruliqueDoru MODRISAN dorulique Data 21 iulie 2015 19:08:41
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char p[2000010],s[2000010];
int q[2000010],poz[1010];

int main()
{
    fstream f("strmatch.in",ios::in);
    f.getline(p,2000010);
    f.getline(s,2000010);
    f.close();
    f.open("strmatch.out",ios::out);
    int i=1,j=0,lp=strlen(p),ls=strlen(s);
    q[0]=0;
    while(i<lp)
        if(p[i]==p[j])
                q[i++]=++j;
        else
            if(j)
                j=q[j-1];
            else
                q[i++]=0;
    int n=0;
    i=0;j=0;
    while(i<ls)
        if(s[i]==p[j])i++,j++;
        else
            if(j)
            {
                if(j==lp&&n<1000)poz[++n]=i-j;
                j=q[j-1];
            }
            else i++;
    f<<n<<"\n";
    for(i=1;i<=min(n,1000);i++)f<<poz[i]<<" ";
    return 0;
}