Cod sursa(job #933535)

Utilizator costyv87Vlad Costin costyv87 Data 30 martie 2013 01:55:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (a[(i)][(j)].c-a[(i)][(j)].f)
using namespace std;
FILE *f,*g;
char A[2000010],B[2000010];
int i,j,n,m;
int v[2000010];
int ans;
vector <int> sol;

void pre()
{
    int i,k;
    fscanf(f,"%s",A);
    n=strlen(A)-1;

    for (k=-1,i=1,v[0]=-1;i<=n;i++)
    {
        while (k>=0 && A[k+1]!=A[i]) k=v[k];
        if (A[k+1]==A[i]) k++;
        v[i]=k;
    }
}

void solve()
{
    int i,k;
    fscanf(f,"%s",B);
    m=strlen(B)-1;

    for (k=-1,i=0;i<=m;i++)
    {
        while (k>=0 && A[k+1]!=B[i]) k=v[k];
        if (A[k+1]==B[i]) k++;
        if (k==n)
        {
            ans++;
            if (sol.size()<1000) sol.push_back(i-n);
        }
    }
}

int main()
{
    f=fopen("strmatch.in","r");
    g=fopen("strmatch.out","w");

    pre();
    solve();
    fprintf(g,"%d\n",ans);
    for (i=0;i<sol.size();i++) fprintf(g,"%d ",sol[i]);

	return 0;
}