Cod sursa(job #1106277)

Utilizator lehman97Dimulescu David lehman97 Data 12 februarie 2014 18:09:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");


int urm[2100005],q,v[2100005],i,n,m;
char s1[2100005],s2[2100005],s3[2100005]=" ";
void urmator(char s1[2100005])
{
    int k,i;
    k=0;
    for(i=2;i<=m;i++)
    {
        while(k>0 && s1[i]!=s1[k+1])k=urm[k];
        if(s1[k+1]==s1[i]) k++;
        urm[i]=k;
    }
}

int main()
{
    fgets(s1,2100005,f);
    strcpy(s1+strlen(s1)-1,s1+strlen(s1));
    m=strlen(s1);
    strcat(s3,s1);
    strcpy(s1,s3);
    fgets(s2,2100005,f);
    strcpy(s2+strlen(s2)-1,s1+strlen(s2));
    n=strlen(s2);
    strcpy(s3," ");
    strcat(s3,s2);
    strcpy(s2,s3);

    urmator(s1);

    q=0;
    for(i=1;i<=n;i++)
    {
        while(q>0 && s1[q+1]!=s2[i])q=urm[q];
        if(s1[q+1]==s2[i]) q++;
        if(q==m)
        {
            v[++v[0]]=i-m;
        }
    }
    fprintf(g,"%d\n",v[0]);
    for(i=1;i<=min(v[0],1000);i++)
    fprintf(g,"%d ",v[i]);
    fclose(g);

    return 0;
}