Cod sursa(job #1621897)

Utilizator Mr.RobotElliot Alderson Mr.Robot Data 29 februarie 2016 22:45:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000001], b[2000001];
int v[2000001], c[1001], k;

int main()
{
    f >> a >> b;


    int n = strlen( a );
    int m = strlen( b );

    int i, j;
    i = 0;
    v[ i ] = 0;

    for( j = 1; j < n; j ++ )
    {
        while( i != 0 && a[i] != a[j] )
            i = v[i - 1];
        if( a[i] == a[j] )
        {
            v[j] = i + 1;
            i ++;
        }
        else
            v[j] = 0;
    }

    i = 0;

    for( j = 0; j < m; j ++ )
    {
        while( i != 0 && a[i] != b[j] )
            i = v[ i - 1 ];
        if( a[i] == b[j] )
            i ++ ;
        if( i == n )
        {
             c[ ++ k ] = j - i + 1;
             i = v[i - 1];
        }
        if( k == 1000 )
            break;
    }
    g << k << '\n';
    for( int i = 1; i <= k; i ++ )
        g << c[i] << " ";

    return 0;
}