Cod sursa(job #1647430)

Utilizator gerd13David Gergely gerd13 Data 10 martie 2016 20:33:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
 
 
using namespace std ;
 
const int NMAX = 2000050 ;
const int shortNMAX = 1024 ;
const int INF = 0x3f3f3f3f ;
 
ifstream cin ("strmatch.in") ;
ofstream cout("strmatch.out") ;
 
int N, M;
char A[NMAX], B[NMAX] ;
 
int pi[NMAX], pos[shortNMAX] ;
//string A, B;
 
inline int min(int a, int b)
{
    if(a > b) return b ;
    else return a ;
}
 
inline int max(int a, int b)
{
    if(a < b) return b ;
    else return a ;
}
 
 
inline void prefix()
{
    int i, q = 0 ;
 
    for( i = 2, pi[1] = 0; i <= M ; ++ i)
    {
        while(q && A[q + 1] != A[i])
 
            q = pi[q] ;
        if(A[q + 1] == A[i])
            ++ q ;
        pi[i] = q ;
 
    }
 
 
 
}
 
 
 
int main()
{
 
    //memset(A, NULL, sizeof(A)) ;
    //memset(B, NULL, sizeof(B)) ;
 
 
 
 
    int i, q = 0, n = 0 ;
    cin >> A >> B ;
 
    //cout << A << '\n' << B << '\n' ;
 
    for(; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z') || (A[M] >= '0' && A[M] <= '9'); ++ M);
    for(; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z') || (B[N] >= '0' && B[N] <= '9'); ++ N);
    for(i = M ; i ; -- i) A[i] = A[i - 1];
    A[0] = ' ' ;
    for(i = N ; i ; -- i) B[i] = B[i - 1] ;
    B[0] = ' ' ;
 
 
 
    prefix() ;
 
 
    for(i = 1 ; i <= N ; ++ i)
    {
        while(q && A[q + 1] != B[i])
            q = pi[q] ;
 
        if(A[q + 1] == B[i])
            ++ q ;
 
        if(q == M)
        {
            q = pi[M] ;
            ++ n ;
            if(n <= 1000)
                pos[n] = i - M ;
        }
    }
 
 
 
 
 
 
 
 
 
    cout << n << '\n' ;
 
    for(int j = 1 ; j <= min(n, 1000) ; ++ j)
        cout << pos[j] << ' ' ;
    cout <<  '\n' ;
 
 
 
    cin.close() ;
    cout.close() ;
    return  0 ;
}