Cod sursa(job #1344619)

Utilizator karlaKarla Maria karla Data 16 februarie 2015 21:00:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

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

int n, m, l, aux[2000005];
char s[2000005], a[2000005];
vector<int> sol;

int main()
{
    fscanf(f,"%s\n",s+1);
    fscanf(f,"%s\n",a+1);

    n = strlen(s+1);
    m = strlen(a+1);

    l = 0;
    for(int i = 2; i <= n; i++ )
    {
        while(l > 0 && s[i] != s[l+1])
            l = aux[l];
        if(s[i] == s[l+1])
        {
            l++;
            aux[i] = l;
        }
    }
    int nr = 0;
    l = 0;
    for(int i = 1; i <= m; i++)
    {
        while(l > 0 && a[i] != s[l+1])
            l = aux[l];
        if(a[i] == s[l+1])
        {
            l++;
        }
        if(l == n)
        {
            nr++;
            sol.push_back(i-n);
            l = aux[l];
        }
    }
    fprintf(g,"%d\n",nr);
    for(vector<int>::iterator it = sol.begin(); it != sol.end(); it++)
    {
        fprintf(g,"%d ", *it);
    }

    return 0;
}