Pagini recente » Cod sursa (job #2720600) | Cod sursa (job #2823160)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");;
ofstream fout("strmatch.out");
/// caut pe s in t
/// afisare nr de aparitii si pozitiile acestora
int ct;
queue <int> poz;
char t[N],s[N];
int table[N];
int n,m;
/// n ----- t
/// m ----- s
void Generare()
{
int i;
i=0;
table[0]=0;
for(int j=1;j<m;j++)
{
while( i>=1 and s[i]!=s[j] )
i=table[i-1];
if( s[i]==s[j] )i++;
table[j]=i;
}
for(int i=0;i<m;i++)cout << table[i] <<" ";
cout <<"\n";
}
int main()
{
fin >> s >> t;
n=strlen(t);
m=strlen(s);
Generare();
int j=0;
for(int i=0;i<n;i++)
{
while( j>0 and s[j]!=t[i] )
j=table[j-1];
if( t[i]==s[j] )j++;
if( j==m )
{
ct++;
poz.push( i-m+1 );
}
}
fout << ct <<"\n";
for(int i=1;i<=ct and !poz.empty();i++ ){
fout << poz.front()<< " ";poz.pop();
}
return 0;
}