Pagini recente » Cod sursa (job #2916720) | Cod sursa (job #2662590) | Cod sursa (job #3124087) | Cod sursa (job #1071794) | Cod sursa (job #2823110)
#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();
for(int i=0;i<n;i++)
if( t[i]==s[0] )
{
int j=1;
while( t[i+j]==s[j] )j++;
if( j==m ){ct++,poz.push(i);}
else i+=j-table[j-1]-1;
}
fout << ct <<"\n";
while(!poz.empty()){
fout << poz.front()<< " ";poz.pop();
}
return 0;
}