Pagini recente » Cod sursa (job #2033050) | Cod sursa (job #422135) | Cod sursa (job #2577147) | Cod sursa (job #584852) | Cod sursa (job #2673262)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[2000005], s2[2000005];
int prefix[2000005], sol[1005];
int main()
{
fin.getline(s1,NULL);
fin.getline(s2,NULL);
int poz = 0;
int j = 0;
///Prima parte-prefixarea
for(int i = 1; i < strlen(s1); i++)
{
while(s1[i] != s1[j] && j != 0)
j = prefix[j - 1];///prefix[-1] nu exista
if(s1[i] == s1[j])
j++;
prefix[i] = j;///prefix = aux
}
j = 0;
int k = 0;
///Calcularea solutiilor-partea a doua
for(int i = 0 ; i < strlen(s2); i++)
{
while(s2[i] != s1[j] && j != 0)
j = prefix[j - 1];
if(s2[i] == s1[j])
{
j++;
if(j == strlen(s1))
{
k++;
if(k <= 1000)
sol[k] = i - j + 1;
j = prefix[j - 1];
}
}
}
fout << k << '\n';
for(int i = 1; i <= min(1000, k); i++)
fout << sol[i] << " ";
return 0;
}